// 动态修改画板元素

DynamicPositionedGraph = function( drawGraph )
{
    this.DG = drawGraph;

    this._heuristics = new Heuristics( drawGraph ); 

    this._heuristics.improvePositioning();

    this._onlyProbandGraph = [ { name :'proband' } ];
};

DynamicPositionedGraph.makeEmpty = function (layoutRelativePersonWidth, layoutRelativeOtherWidth)
{
    var baseG       = new BaseGraph(layoutRelativePersonWidth, layoutRelativeOtherWidth);
    var positionedG = new PositionedGraph(baseG);
    return new DynamicPositionedGraph(positionedG);
}

DynamicPositionedGraph.prototype = {
		setProbandId: function(id)
        {
            this.DG.probandId = id;
        },

        getProbandId: function()
        {
            return this.DG.probandId;
        },

        getAllPatientLinks: function()
        {
            var linkedPatientsList = { "linkedPatients": [], "patientToNodeMapping": {} };

            for (var i = 0 ; i <= this.getMaxNodeId(); i++) {
                if (this.isPerson(i)) {
                    if (this.getProperties(i).hasOwnProperty("phenotipsId")) {
                        linkedPatientsList.linkedPatients.push( this.getProperties(i).phenotipsId );
                        linkedPatientsList.patientToNodeMapping[this.getProperties(i).phenotipsId] = i;
                    }
                }
            }
            return linkedPatientsList;
        },

        getCurrentPatientId: function()
        {
            return editor.getExternalEndpoint().getParentDocument().id;
        },

        getCurrentPatientNodeID: function()
        {
            var allLinkedNodes = this.getAllPatientLinks();
            if (!allLinkedNodes.patientToNodeMapping.hasOwnProperty(this.getCurrentPatientId())) {
                return null;
            }
            return allLinkedNodes.patientToNodeMapping[this.getCurrentPatientId()];
        },

        getPhenotipsLinkID: function( id ) {
            return this.getProperties(id).hasOwnProperty("phenotipsId") ? this.getProperties(id).phenotipsId : "";
        },

        getPatientDescription: function( id, htmlPatientLink ) {
            var phenotipsId = this.getPhenotipsLinkID(id);
            var space = " ";
            if (htmlPatientLink) {
                var space = "&nbsp;";
                if (phenotipsId != "") {
                    phenotipsId = "<a href='" + editor.getExternalEndpoint().getPhenotipsPatientURL(phenotipsId) + "'>" + phenotipsId + "</a>";
                }
            }
            var props = this.getProperties(id);
            var firstName = props.hasOwnProperty("fName") ? props.fName : "";
            var lastName = props.hasOwnProperty("lName") ? props.lName : "";
            var fullName = firstName + ((firstName != "" && lastName != "") ? space : "") + lastName;
            var description = phenotipsId + ((phenotipsId != "" && fullName != "")? "," + space : "") + fullName;
            return description;
        },
    isValidID: function( id )
    {
      if (id < 0 || id > this.DG.GG.getMaxRealVertexId())
        return false;
      if (!this.DG.GG.isPerson(id) && !this.DG.GG.isRelationship(id))
        return false;
      return true;
    },

    getMaxNodeId: function()
    {
        return this.DG.GG.getMaxRealVertexId();
    },

    isPersonGroup: function( id )
    {
        return this.getProperties(id).hasOwnProperty("numPersons");
    },

    isPerson: function( id )
    {
        return this.DG.GG.isPerson(id);
    },

    isRelationship: function( id )
    {
        return this.DG.GG.isRelationship(id);
    },

    isPlaceholder: function( id )
    {
        if (!this.isPerson(id)) return false;
        return false;
    },

    isAdopted: function( id )
    {
        if (!this.isPerson(id))
            throw "Assertion failed: isAdopted() is applied to a non-person";
        return this.DG.GG.isAdopted(id);
    },

    getGeneration: function( id )
    {
        var minRank = Math.min.apply(null, this.DG.ranks);
        return (this.DG.ranks[id] - minRank)/2 + 1;
    },

    getOrderWithinGeneration: function( id )
    {
        if (!this.isPerson(id))
            throw "Assertion failed: getOrderWithinGeneration() is applied to a non-person";

        var order = 0;
        var rank  = this.DG.ranks[id];
        for (var i = 0; i < this.DG.order.order[rank].length; i++) {
            var next = this.DG.order.order[rank][i];
            if (this.DG.GG.isPerson(next)) order++;
            if (next == id) break;
        }
        return order;
    },
 	getGroupType: function(id)
    {	return this.DG.GG.getGroupType(id);
    },
    

    getTwinGroupId: function( id )
    {
        return this.DG.GG.getTwinGroupId(id);
    },

    getAllTwinsSortedByOrder: function( id )
    {
        var twins = this.DG.GG.getAllTwinsOf(id);
        var vOrder = this.DG.order.vOrder;
        var byOrder = function(a,b){ return vOrder[a] - vOrder[b]; };
        twins.sort( byOrder );
        return twins;
    },

    isChildless: function( id )
    {
        if (!this.getProperties(id).hasOwnProperty("childlessStatus"))
            return false;
        var res =  (this.getProperties(id)["childlessStatus"] !== null);
        return res;
    },

    isConsangrRelationship: function( id )
    {
        if (!this.isRelationship(id))
            throw "Assertion failed: isConsangrRelationship() is applied to a non-relationship";

        return this.DG.consangr.hasOwnProperty(id);
    },

    getProperties: function( id )
    {
        return this.DG.GG.properties[id];
    },

    setProperties: function( id, newSetOfProperties )
    {
        this.DG.GG.properties[id] = newSetOfProperties;
    },

    setProbandData: function( firstName, lastName, gender ,precursor)
    {
        var ret = true;
        for(var i=0;i<this.DG.GG.properties.length;i++){
            var node = this.DG.GG.properties[i];
            if(node.precursor == 1){
                node.fName = firstName;
                node.lName = lastName;
                node.precursor = precursor;
                this.setProbandId(node.precursor);
                var setGender = gender;
                var possibleGenders = this.getPossibleGenders(i);
                if (!possibleGenders.hasOwnProperty(gender) || !possibleGenders[gender])
                    setGender = 'U'
                    node.gender = setGender;
                ret = false;
                break;
            }
        }
        if(ret){
            this.DG.GG.properties[0].precursor = 1;
        }
        return (gender == setGender);
    },

    getPosition: function( v )
    {
        var x = this.DG.positions[v];

        var rank = this.DG.ranks[v];

        var vertLevel = this.DG.GG.isChildhub(v) ? this.DG.vertLevel.childEdgeLevel[v] : 1;

        var y = this.DG.computeNodeY(rank, vertLevel);

        if (this.DG.GG.isVirtual(v)) {
            var relId    = this.DG.GG.downTheChainUntilNonVirtual(v);
            var personId = this.DG.GG.upTheChainUntilNonVirtual(v);

            var rankPerson = this.DG.ranks[personId];
            if (rank == rankPerson) {
                var level = this.DG.vertLevel.outEdgeVerticalLevel[personId][relId].verticalLevel;
                y = this.DG.computeRelLineY(rank, 0, level).relLineY;
            }

            var rankRelationship = this.DG.ranks[relId];
            if (rank == rankRelationship) {
                y = this.getPosition(relId).y;
            }
        }
        else
        if (this.isRelationship(v)) {
            var partners = this.DG.GG.getParents(v);
            var level1   = this.DG.vertLevel.outEdgeVerticalLevel[partners[0]].hasOwnProperty(v) ? this.DG.vertLevel.outEdgeVerticalLevel[partners[0]][v].verticalLevel : 0;
            var level2   = this.DG.vertLevel.outEdgeVerticalLevel[partners[1]].hasOwnProperty(v) ? this.DG.vertLevel.outEdgeVerticalLevel[partners[1]][v].verticalLevel : 0;
            var level    = Math.min(level1, level2);
            var attach1  = this.DG.vertLevel.outEdgeVerticalLevel[partners[0]].hasOwnProperty(v) ? this.DG.vertLevel.outEdgeVerticalLevel[partners[0]][v].attachlevel : 0;
            var attach2  = this.DG.vertLevel.outEdgeVerticalLevel[partners[1]].hasOwnProperty(v) ? this.DG.vertLevel.outEdgeVerticalLevel[partners[1]][v].attachlevel : 0;
            var attach   = Math.min(attach1, attach2);
            y = this.DG.computeRelLineY(rank, attach, level).relLineY;
        }

        return {"x": x, "y": y};
    },

    getRelationshipChildhubPosition: function( v )
    {
        if (!this.isRelationship(v))
            throw "Assertion failed: getRelationshipChildhubPosition() is applied to a non-relationship";

        var childhubId = this.DG.GG.getRelationshipChildhub(v);

        return this.getPosition(childhubId);
    },

    getRelationshipLineInfo: function( relationship, person )
    {
        if (!this.isRelationship(relationship))
            throw "Assertion failed: getRelationshipToPersonLinePosition() is applied to a non-relationship";
        if (!this.isPerson(person))
            throw "Assertion failed: getRelationshipToPersonLinePosition() is applied to a non-person";

        var info = this.DG.vertLevel.outEdgeVerticalLevel[person].hasOwnProperty(relationship) ?
                   this.DG.vertLevel.outEdgeVerticalLevel[person][relationship] :
                   { attachlevel: 0, verticalLevel: 0, numAttachLevels: 1 };


        var verticalRelInfo = this.DG.computeRelLineY(this.DG.ranks[person], info.attachlevel, info.verticalLevel);

        var result = {"attachmentPort": info.attachlevel,
                      "attachY":        verticalRelInfo.attachY,
                      "verticalLevel":  info.verticalLevel,
                      "verticalY":      verticalRelInfo.relLineY,
                      "numAttachPorts": info.numAttachLevels };

        return result;
    },

    getRelationshipChildrenSortedByOrder: function( v )
    {
        if (!this.isRelationship(v))
            throw "Assertion failed: getRelationshipChildren() is applied to a non-relationship";

        var childhubId = this.DG.GG.getRelationshipChildhub(v);

        var children = this.DG.GG.getOutEdges(childhubId);

        var vOrder = this.DG.order.vOrder;
        var byOrder = function(a,b){ return vOrder[a] - vOrder[b]; };
        children.sort( byOrder );

        return children;
    },

    getAllChildren: function( v )
    {
        if (!this.isPerson(v) && !this.isRelationship(v))
            throw "Assertion failed: getAllChildren() is applied to a non-person non-relationship node";

        var rels = this.isRelationship(v) ? [v] : this.DG.GG.getAllRelationships(v);

        var allChildren = [];
        for (var i = 0; i < rels.length; i++) {
            var chhub    = this.DG.GG.getOutEdges(rels[i])[0];
            var children = this.DG.GG.getOutEdges(chhub);

            allChildren = allChildren.concat(children);
        }
        return allChildren;
    },

    isChildOfProband: function( v )
    {
        var parents = this.DG.GG.getParents(v);
        if (arrayContains(parents,0)) return true;
        return false;
    },

    isPartnershipRelatedToProband: function( v )
    {
        var parents = this.DG.GG.getParents(v);
        if (arrayContains(parents, 0)) return true;
        if (v == this.DG.GG.getProducingRelationship(0))
        {
            return true;
        }
        return false;
    },

    isRelatedToProband: function( v )
    {
        var probandRelatedRels = this.getAllRelatedRelationships(0);
        for (var i = 0; i < probandRelatedRels.length; i++) {
            var rel = probandRelatedRels[i];

            var parents = this.DG.GG.getParents(rel);
            if (arrayContains(parents, v)) return true;

            var children = this.getAllChildren(rel);
            if (arrayContains(children, v)) return true;
        }
        return false;
    },

    getAllRelatedRelationships: function( v )
    {
        var allRels = this.DG.GG.getAllRelationships(v);
        var parentRel = this.DG.GG.getProducingRelationship(v);
        if (parentRel != null) {
            allRels.push(parentRel);
        }
        return allRels;
    },

    hasNonPlaceholderNonAdoptedChildren: function( v )
    {
        if (this.isRelationship(v)) {
            var children = this.getRelationshipChildrenSortedByOrder(v);

            for (var i = 0; i < children.length; i++) {
                var child = children[i];
                if (!this.isPlaceholder(child) && !this.isAdopted(child)) {
                    return true;
                }
            }
        }
        else if (this.isPerson(v)) {
            //TODO
        }

        return false;
    },

    getParentRelationship: function( v )
    {
        if (!this.isPerson(v))
            throw "Assertion failed: getParentRelationship() is applied to a non-person";

        return this.DG.GG.getProducingRelationship(v);
    },

    hasToBeAdopted: function( v )
    {
        if (!this.isPerson(v))
            throw "Assertion failed: hasToBeAdopted() is applied to a non-person";

        var parentRel = this.getParentRelationship(v);
        if (parentRel !== null && this.isChildless(parentRel))
            return true;
        return false;
    },

    hasRelationships: function( v )
    {
        if (!this.isPerson(v))
            throw "Assertion failed: hasRelationships() is applied to a non-person";

        return (this.DG.GG.v[v].length > 0); // if it had relationships it must have been alive at some point
    },

    getPossibleGenders: function( v )
    {
        var possible = {"M": true, "F": true, "U": true};
        var partners = this.DG.GG.getAllPartners(v);

        var knownGenderPartner = undefined;
        for (var i = 0; i < partners.length; i++) {
            var partnerGender = this.getGender(partners[i]);
            if (partnerGender != "U") {
                possible[partnerGender] = false;
                break;
            }
        }

        return possible;
    },

    getPossibleChildrenOf: function( v )
    {
        var result = [];
        for (var i = 0; i <= this.DG.GG.getMaxRealVertexId(); i++) {
           if (!this.isPerson(i)) continue;
           if (this.DG.GG.inedges[i].length != 0) continue;
           if (this.DG.ancestors[v].hasOwnProperty(i)) continue;
           result.push(i);
        }
        return result;
    },

    getPossibleSiblingsOf: function( v )
    {
        var hasParents = (this.getParentRelationship(v) !== null);
        var result = [];
        for (var i = 0; i <= this.DG.GG.getMaxRealVertexId(); i++) {
           if (!this.isPerson(i)) continue;
           if (this.DG.ancestors[v].hasOwnProperty(i)) continue;
           if (this.DG.ancestors[i].hasOwnProperty(v)) continue;
           if (hasParents && this.DG.GG.inedges[i].length != 0) continue;
           result.push(i);
        }
        return result;
    },

    getPossibleParentsOf: function( v )
    {
        var result = [];
        for (var i = 0; i <= this.DG.GG.getMaxRealVertexId(); i++) {
           if (!this.isRelationship(i) && !this.isPerson(i)) continue;
           if (this.isPersonGroup(i)) continue;
           if (this.DG.ancestors[i].hasOwnProperty(v)) continue;
           result.push(i);
        }
        return result;
    },

    getPossiblePartnersOf: function( v )
    {
        var oppositeGender  = this.DG.GG.getOppositeGender(v);
        var validGendersSet = (oppositeGender == 'U') ? ['M','F','U'] : [oppositeGender,'U'];

        var result = this._getAllPersonsOfGenders(validGendersSet);

        var partners = this.DG.GG.getAllPartners(v);
        partners.push(v);
        for (var i = 0; i < partners.length; i++)
            removeFirstOccurrenceByValue( result, partners[i] );

        return result;
    },

    getOppositeGender: function( v )
    {
        if (!this.isPerson(v))
            throw "Assertion failed: getOppositeGender() is applied to a non-person";

        return this.DG.GG.getOppositeGender(v);
    },

    getGender: function( v )
    {
        if (!this.isPerson(v))
            throw "Assertion failed: getGender() is applied to a non-person";

        return this.DG.GG.getGender(v);
    },

    getDisconnectedSetIfNodeRemoved: function( v )
    {
        var removedList = {};
        removedList[v] = true;

        if (this.isPerson(v)) {
            if (this.DG.GG.getInEdges(v).length != 0) {
                var chhub = this.DG.GG.getInEdges(v)[0];
                if (this.DG.GG.getOutEdges(chhub).length == 1) {
                    removedList[ this.DG.GG.getInEdges(chhub)[0] ] = true;
                }
            }

            var allRels = this.DG.GG.getAllRelationships(v);
            for (var i = 0; i < allRels.length; i++) {
                removedList[allRels[i]] = true;
            }
        }

        for (var node in removedList) {
            if (removedList.hasOwnProperty(node) && this.isRelationship(node)) {
                var chhubId = this.DG.GG.getOutEdges(node)[0];
                removedList[chhubId] = true;
            }
        }

        var connected = {};

        var queue = new Queue();
        queue.push( 0 );

        while ( queue.size() > 0 ) {
            var next = parseInt(queue.pop());

            if (connected.hasOwnProperty(next)) continue;
            connected[next] = true;

            var outEdges = this.DG.GG.getOutEdges(next);
            for (var i = 0; i < outEdges.length; i++) {
                if (!removedList.hasOwnProperty(outEdges[i]))
                    queue.push(outEdges[i]);
            }
            var inEdges = this.DG.GG.getInEdges(next);
            for (var i = 0; i < inEdges.length; i++) {
                if (!removedList.hasOwnProperty(inEdges[i]))
                    queue.push(inEdges[i]);
            }
        }
        console.log("Connected nodes: " + stringifyObject(connected));

        var affected = [];
        for (var i = 0; i < this.DG.GG.getNumVertices(); i++) {
            if (this.isPerson(i) || this.isRelationship(i)) {
                if (!connected.hasOwnProperty(i))
                    affected.push(i);
            }
        }

        console.log("Affected nodes: " + stringifyObject(affected));
        return affected;
    },

    _debugPrintAll: function( headerMessage )
    {
        console.log("========== " + headerMessage + " ==========");
    },

    updateAncestors: function()  
    {
        var ancestors = this.DG.findAllAncestors();
        this.DG.ancestors = ancestors.ancestors;
        this.DG.consangr  = ancestors.consangr;

        var movedNodes = [];
        for (var i = 0; i <= this.DG.GG.getMaxRealVertexId(); i++) {
            if (!this.isRelationship(i)) continue;
            movedNodes.push(i);
        }

        return { "moved": movedNodes };
    },
	/*
	 * 1、partnershipID
	 * @partnershipID, childParams, numTwins, numBrothers, numSisters, numUnknowns 
	 * childParams: 
	 */
    addNewChild: function( childhubId, properties, numTwins, numBrothers, numSisters, numUnknowns )
    {
        this._debugPrintAll("before");
        var timer = new Timer();

        if (!this.DG.GG.isChildhub(childhubId)) {
            if (this.DG.GG.isRelationship(childhubId))
                childhubId = this.DG.GG.getRelationshipChildhub(childhubId);
            else
                throw "添加失败";
        }

        var positionsBefore  = this.DG.positions.slice(0);
        var ranksBefore      = this.DG.ranks.slice(0);
        var vertLevelsBefore = this.DG.vertLevel.copy();
        var rankYBefore      = this.DG.rankY.slice(0);
        var numNodesBefore   = this.DG.GG.getMaxRealVertexId();

        if (!properties) properties = {};
        if (!numTwins) numTwins = 1;
        if (!numBrothers) numBrothers = 1;
        if (!numSisters) numSisters = 1;
        if (!numUnknowns) numUnknowns = 1;

        var insertRank = this.DG.ranks[childhubId] + 1;

        var insertOrder = this._findBestInsertPosition( insertRank, childhubId );

        var newNodeId = this._insertVertex(TYPE.PERSON, properties, 1.0, childhubId, null, insertRank, insertOrder);
		var grouptwins = false;
		var groupbrothers = false;
		var groupsisters = false;
		var groupunknowns = false;
		if(numTwins > 1){
			grouptwins = true;
			var groupType = "isGroupTwins";
		} else if(numBrothers > 1){
			groupbrothers = true;
			var groupType = "isGroupbrothers";
		} else if(numSisters > 1){
			groupsisters = true;
			var groupType = "isGroupsisters";
		} else if(numUnknowns > 1){
			groupunknowns = true;
			var groupType = "isGroupunknowns";
		} else {
			var groupType = "none";
		}
		
        var newNodes = [newNodeId];
        for (var i = 0; i < numTwins - 1; i++ ) {
        		if(i > 2) {grouptwins = true;}
            var changeSet = this.addTwin( newNodeId, properties, groupType);
            newNodes.push(changeSet["new"][0]);
        }
        for (var i = 0; i < numBrothers - 1; i++ ) {
        		if(i > 2) {groupbrothers = true;}
            var changeSet = this.addTwin( newNodeId, properties, groupType);
            newNodes.push(changeSet["new"][0]);
        }
        for (var i = 0; i < numSisters - 1; i++ ) {
        		if(i > 2) {groupsisters = true;}
            var changeSet = this.addTwin( newNodeId, properties, groupType);
            newNodes.push(changeSet["new"][0]);
        }
        for (var i = 0; i < numUnknowns - 1; i++ ) {
        		if(i > 2) {groupunknowns = true;}
            var changeSet = this.addTwin( newNodeId, properties, groupType);
            newNodes.push(changeSet["new"][0]);
        }

        this.DG.GG.validate();

        this._heuristics.improvePositioning(ranksBefore, rankYBefore);

        this.updateAncestors();

        timer.printSinceLast("=== AddChild runtime: ");
        this._debugPrintAll("after");

        var movedNodes = this._findMovedNodes( numNodesBefore, positionsBefore, ranksBefore, vertLevelsBefore, rankYBefore );
        var relationshipId = this.DG.GG.getInEdges(childhubId)[0];
        if (!arrayContains(movedNodes,relationshipId))
            movedNodes.push(relationshipId);
        var animateNodes = this.DG.GG.getInEdges(relationshipId);  
        return {"new": newNodes, "moved": movedNodes, "animate": animateNodes};
    },

    addNewParents: function( personId )
    {
        this._debugPrintAll("before");
        var timer = new Timer();

        if (!this.DG.GG.isPerson(personId))
            throw "非个体节点";

        if (this.DG.GG.getInEdges(personId).length > 0)
            throw "已存在父节点";

        var positionsBefore  = this.DG.positions.slice(0);
        var ranksBefore      = this.DG.ranks.slice(0);
        var vertLevelsBefore = this.DG.vertLevel.copy();
        var rankYBefore      = this.DG.rankY.slice(0);
        var numNodesBefore   = this.DG.GG.getMaxRealVertexId();

        this._heuristics.swapBeforeParentsToBringToSideIfPossible( personId );

        var insertChildhubRank = this.DG.ranks[personId] - 1;

        var insertChildhubOrder = this._findBestInsertPosition( insertChildhubRank, personId );

        var newChildhubId = this._insertVertex(TYPE.CHILDHUB, {}, 1.0, null, personId, insertChildhubRank, insertChildhubOrder);

        var insertParentsRank = this.DG.ranks[newChildhubId] - 1;  

        var insertParentOrder = this._findBestInsertPosition( insertParentsRank, newChildhubId );

        var newRelationshipId = this._insertVertex(TYPE.RELATIONSHIP, {}, 1.0, null, newChildhubId, insertParentsRank, insertParentOrder);

        insertParentsRank = this.DG.ranks[newRelationshipId];       
                                                                    
        var newParent1Id = this._insertVertex(TYPE.PERSON, {"gender": "F"}, 1.0, null, newRelationshipId, insertParentsRank, insertParentOrder + 1);
        var newParent2Id = this._insertVertex(TYPE.PERSON, {"gender": "M"}, 1.0, null, newRelationshipId, insertParentsRank, insertParentOrder);

        this.DG.GG.validate();

        this._heuristics.improvePositioning(ranksBefore, rankYBefore);

        this.updateAncestors();

        timer.printSinceLast("=== NewParents runtime: ");
        this._debugPrintAll("after");

        var animateNodes = this.DG.GG.getAllPartners(personId);
        if (animateNodes.length == 1)  
            animateNodes.push(personId);
        else
            animateNodes = [personId];
        var movedNodes = this._findMovedNodes( numNodesBefore, positionsBefore, ranksBefore, vertLevelsBefore, rankYBefore );
        var newNodes   = [newRelationshipId, newParent1Id, newParent2Id];
        return {"new": newNodes, "moved": movedNodes, "highlight": [personId], "animate": animateNodes};
    },

    addNewRelationship: function( personId, childProperties, preferLeft, numTwins, numBrothers, numSisters, numUnknowns )
    {
        this._debugPrintAll("before");
        var timer = new Timer();

        if (!this.DG.GG.isPerson(personId))
            throw "非个体节点";

        var positionsBefore  = this.DG.positions.slice(0);
        var ranksBefore      = this.DG.ranks.slice(0);
        var vertLevelsBefore = this.DG.vertLevel.copy();
        var rankYBefore      = this.DG.rankY.slice(0);
        var consangrBefore   = this.DG.consangr;
        var numNodesBefore   = this.DG.GG.getMaxRealVertexId();

        if (!childProperties) childProperties = {};

        if (!numTwins) numTwins = 1;
        //==
        if (!numBrothers) numBrothers = 1;
        if (!numSisters) numSisters = 1;
        if (!numUnknowns) numUnknowns = 1;
        //==

        var partnerProperties = { "gender": this.DG.GG.getOppositeGender(personId) };

        var insertRank  = this.DG.ranks[personId];
        var personOrder = this.DG.order.vOrder[personId];

        this._heuristics.swapPartnerToBringToSideIfPossible( personId );
        this._heuristics.swapTwinsToBringToSideIfPossible( personId );

        var insertOrder = this._findBestInsertPosition( insertRank, personId, preferLeft );

        console.log("vOrder: " + personOrder + ", inserting @ " + insertOrder);
        console.log("Orders before: " + stringifyObject(this.DG.order.order[this.DG.ranks[personId]]));

        var newRelationshipId = this._insertVertex(TYPE.RELATIONSHIP, {}, 1.0, personId, null, insertRank, insertOrder);

        console.log("Orders after: " + stringifyObject(this.DG.order.order[this.DG.ranks[personId]]));

        var insertPersonOrder = (insertOrder > personOrder) ? insertOrder + 1 : insertOrder;

        var newPersonId = this._insertVertex(TYPE.PERSON, partnerProperties, 1.0, null, newRelationshipId, insertRank, insertPersonOrder);

        var insertChildhubRank  = insertRank + 1;
        var insertChildhubOrder = this._findBestInsertPosition( insertChildhubRank, newRelationshipId );
        var newChildhubId       = this._insertVertex(TYPE.CHILDHUB, {}, 1.0, newRelationshipId, null, insertChildhubRank, insertChildhubOrder);

        var insertChildRank  = insertChildhubRank + 1;
        var insertChildOrder = this._findBestInsertPosition( insertChildRank, newChildhubId );
        var newChildId       = this._insertVertex(TYPE.PERSON, childProperties, 1.0, newChildhubId, null, insertChildRank, insertChildOrder);

		var grouptwins = false;
		var groupbrothers = false;
		var groupsisters = false;
		var groupunknowns = false;
		if(numTwins > 1){
			grouptwins = true;
			var groupType = groupTwins;
		} else if(numBrothers > 1){
			groupbrothers = true;
			var groupType = numBrothers;
		} else if(numSisters > 1){
			groupsisters = true;
			var groupType = groupsisters;
		} else if(numUnknowns > 1){
			groupunknowns = true;
			var groupType = groupunknowns;
		} else {
			var groupType = false;
		}

        var newNodes = [newRelationshipId, newPersonId, newChildId];
        for (var i = 0; i < numTwins - 1; i++ ) {
            var changeSet = this.addTwin( newChildId, childProperties, groupType);
            newNodes.push(changeSet["new"][0]);
        }
        
        for (var i = 0; i < numBrothers - 1; i++ ) {
            var changeSet = this.addTwin( newChildId, childProperties, groupType);
            newNodes.push(changeSet["new"][0]);
        }
        for (var i = 0; i < numSisters - 1; i++ ) {
            var changeSet = this.addTwin( newChildId, childProperties, groupType);
            newNodes.push(changeSet["new"][0]);
        }
        for (var i = 0; i < numUnknowns - 1; i++ ) {
            var changeSet = this.addTwin( newChildId, childProperties, groupType);
            newNodes.push(changeSet["new"][0]);
        }
        
        

        console.log("Orders after all: " + stringifyObject(this.DG.order.order[this.DG.ranks[personId]]));

        this.DG.GG.validate();

        this._heuristics.improvePositioning(ranksBefore, rankYBefore);

        this.updateAncestors();

        timer.printSinceLast("=== NewRelationship runtime: ");
        this._debugPrintAll("after");

        var movedNodes = this._findMovedNodes( numNodesBefore, positionsBefore, ranksBefore, vertLevelsBefore, rankYBefore, consangrBefore );
        return {"new": newNodes, "moved": movedNodes, "highlight": [personId]};
    },

    assignParent: function( parentId, childId )
    {
        if (this.isRelationship(parentId)) {
            var childHubId   = this.DG.GG.getRelationshipChildhub(parentId);
            var rankChildHub = this.DG.ranks[childHubId];
            var rankChild    = this.DG.ranks[childId];

            var weight = 1;
            this.DG.GG.addEdge(childHubId, childId, weight);

            var animateList = [childId];

            if (rankChildHub != rankChild - 1) {
                return this.redrawAll(animateList);
            }

            var positionsBefore  = this.DG.positions.slice(0);
            var ranksBefore      = this.DG.ranks.slice(0);
            var vertLevelsBefore = this.DG.vertLevel.copy();
            var rankYBefore      = this.DG.rankY.slice(0);
            var consangrBefore   = this.DG.consangr;
            var numNodesBefore   = this.DG.GG.getMaxRealVertexId();


            this.DG.GG.validate();

            this._updateauxiliaryStructures(ranksBefore, rankYBefore);

            positionsBefore[parentId] = Infinity; 
            var movedNodes = this._findMovedNodes( numNodesBefore, positionsBefore, ranksBefore, vertLevelsBefore, rankYBefore, consangrBefore );
            return {"moved": movedNodes, "animate": [childId]};
        }
        else {
            var rankParent = this.DG.ranks[parentId];
            var rankChild  = this.DG.ranks[childId];

            var partnerProperties = { "gender": this.DG.GG.getOppositeGender(parentId) };


            if (rankParent >= rankChild) {
                var ranksBefore        = this.DG.ranks.slice(0);
                var insertChildhubRank = rankChild - 1;
                var newChildhubId      = this._insertVertex(TYPE.CHILDHUB, {}, 1.0, null, childId, insertChildhubRank, 0);
                var insertParentsRank  = this.DG.ranks[newChildhubId] - 1;   // note: rank may have changed since last insertion
                var newRelationshipId  = this._insertVertex(TYPE.RELATIONSHIP, {}, 1.0, null, newChildhubId, insertParentsRank, 0);
                var newParentId        = this._insertVertex(TYPE.PERSON, partnerProperties, 1.0, null, newRelationshipId, insertParentsRank, 0);
                this.DG.GG.addEdge(parentId, newRelationshipId, 1);
                var animateList = [childId, parentId];
                var newList     = [newRelationshipId, newParentId];
                return this.redrawAll(animateList, newList, ranksBefore);
            }


            this._debugPrintAll("before");
            var timer = new Timer();

            var positionsBefore  = this.DG.positions.slice(0);
            var ranksBefore      = this.DG.ranks.slice(0);
            var vertLevelsBefore = this.DG.vertLevel.copy();
            var rankYBefore      = this.DG.rankY.slice(0);
            var consangrBefore   = this.DG.consangr;
            var numNodesBefore   = this.DG.GG.getMaxRealVertexId();

            var x_parent     = this.DG.positions[parentId];
            var x_child      = this.DG.positions[childId];

            if (rankParent == rankChild - 2) {
                var preferLeft = (x_child < x_parent);

                var insertRelatOrder  = this._findBestInsertPosition( rankParent, parentId, preferLeft);
                var newRelationshipId = this._insertVertex(TYPE.RELATIONSHIP, {}, 1.0, parentId, null, rankParent, insertRelatOrder);

                var newParentOrder = (this.DG.order.vOrder[parentId] > this.DG.order.vOrder[newRelationshipId]) ? insertRelatOrder : (insertRelatOrder+1);
                var newParentId    = this._insertVertex(TYPE.PERSON, partnerProperties, 1.0, null, newRelationshipId, rankParent, newParentOrder);

                var insertChildhubRank  = rankChild - 1;
                var insertChildhubOrder = this._findBestInsertPosition( insertChildhubRank, newRelationshipId );
                var newChildhubId       = this._insertVertex(TYPE.CHILDHUB, {}, 1.0, newRelationshipId, null, insertChildhubRank, insertChildhubOrder);

                this.DG.GG.addEdge(newChildhubId, childId, 1);
            } else {

                var insertChildhubRank  = rankChild - 1;
                var insertChildhubOrder = this._findBestInsertPosition( insertChildhubRank, childId );
                var newChildhubId       = this._insertVertex(TYPE.CHILDHUB, {}, 1.0, null, childId, insertChildhubRank, insertChildhubOrder);

                var insertParentsRank = rankChild - 2;

                var insertRelatOrder  = this._findBestInsertPosition( insertParentsRank, newChildhubId );
                var newRelationshipId = this._insertVertex(TYPE.RELATIONSHIP, {}, 1.0, null, newChildhubId, insertParentsRank, insertRelatOrder);

                var newParentOrder = (this.DG.positions[parentId] > this.DG.positions[newRelationshipId]) ? insertRelatOrder : (insertRelatOrder+1);
                var newParentId    = this._insertVertex(TYPE.PERSON, partnerProperties, 1.0, null, newRelationshipId, insertParentsRank, newParentOrder);

                this._addMultiRankEdge(parentId, newRelationshipId);
            }

            this.DG.GG.validate();

            this._heuristics.improvePositioning(ranksBefore, rankYBefore);

            this.updateAncestors();

            timer.printSinceLast("=== DragToParentOrChild runtime: ");
            this._debugPrintAll("after");

            if (this.DG.positions.length >= 31)
                console.log("position of node 32: " + this.DG.positions[32] + ", was: " + positionsBefore[32]);
            var movedNodes = this._findMovedNodes( numNodesBefore, positionsBefore, ranksBefore, vertLevelsBefore, rankYBefore, consangrBefore );
            var newNodes   = [newRelationshipId, newParentId];
            return {"new": newNodes, "moved": movedNodes, "highlight": [parentId, newParentId, childId]};
        }

    },

    assignPartner: function( person1, person2, childProperties ) {
        var positionsBefore  = this.DG.positions.slice(0);
        var ranksBefore      = this.DG.ranks.slice(0);
        var vertLevelsBefore = this.DG.vertLevel.copy();
        var rankYBefore      = this.DG.rankY.slice(0);
        var consangrBefore   = this.DG.consangr;
        var numNodesBefore   = this.DG.GG.getMaxRealVertexId();

        var rankP1 = this.DG.ranks[person1];
        var rankP2 = this.DG.ranks[person2];

        if (rankP1 < rankP2 ||
            (rankP1 == rankP2 && this.DG.order.vOrder[person2] < this.DG.order.vOrder[person1])
           ) {
            var tmpPerson = person2;
            person2       = person1;
            person1       = tmpPerson;

            rankP1 = rankP2;
            rankP2 = this.DG.ranks[person2];
        }

        var x_person1 = this.DG.positions[person1];
        var x_person2 = this.DG.positions[person2];

        var weight = 1;

        var preferLeft        = (x_person2 < x_person1);
        var insertRelatOrder  = (rankP1 == rankP2) ? this._findBestRelationshipPosition( person1, false, person2 ) :
                                                     this._findBestRelationshipPosition( person1, preferLeft);
        var newRelationshipId = this._insertVertex(TYPE.RELATIONSHIP, {}, weight, person1, null, rankP1, insertRelatOrder);

        var insertChildhubRank  = this.DG.ranks[newRelationshipId] + 1;
        var insertChildhubOrder = this._findBestInsertPosition( insertChildhubRank, newRelationshipId );
        var newChildhubId       = this._insertVertex(TYPE.CHILDHUB, {}, 1.0, newRelationshipId, null, insertChildhubRank, insertChildhubOrder);

        var insertChildRank  = insertChildhubRank + 1;
        var insertChildOrder = this._findBestInsertPosition( insertChildRank, newChildhubId );
        var newChildId       = this._insertVertex(TYPE.PERSON, childProperties, 1.0, newChildhubId, null, insertChildRank, insertChildOrder);

        if (rankP1 == rankP2) {
            this.DG.GG.addEdge(person2, newRelationshipId, weight);
        } else {
            this._addMultiRankEdge(person2, newRelationshipId);
        }

        this.DG.GG.validate();

        this._heuristics.improvePositioning(ranksBefore, rankYBefore);

        this.updateAncestors();

        this._debugPrintAll("after");

        var movedNodes = this._findMovedNodes( numNodesBefore, positionsBefore, ranksBefore, vertLevelsBefore, rankYBefore, consangrBefore );
        var newNodes   = [newRelationshipId, newChildId];
        return {"new": newNodes, "moved": movedNodes, "highlight": [person1, person2, newChildId]};
    },

    addTwin: function( personId, properties, groupType)
    {	
        var positionsBefore  = this.DG.positions.slice(0);
        var ranksBefore      = this.DG.ranks.slice(0);
        var vertLevelsBefore = this.DG.vertLevel.copy();
        var rankYBefore      = this.DG.rankY.slice(0);
        var numNodesBefore   = this.DG.GG.getMaxRealVertexId();

        var parentRel = this.DG.GG.getProducingRelationship(personId);
		
        var twinGroupId = this.DG.GG.getTwinGroupId(personId);
        if (twinGroupId === null) {
            twinGroupId = this.DG.GG.getUnusedTwinGroupId(parentRel);
            console.log("new twin id: " + twinGroupId);
            this.DG.GG.properties[personId]['twinGroup'] = twinGroupId;
        }
        properties['twinGroup'] = twinGroupId;
        properties['groupType'] = groupType;

        var insertRank = this.DG.ranks[personId];

        var insertOrder = this.DG.findBestTwinInsertPosition(personId, []);

        var childhubId = this.DG.GG.getInEdges(personId)[0];
        var newNodeId = this._insertVertex(TYPE.PERSON, properties, 1.0, childhubId, null, insertRank, insertOrder);

        this.DG.GG.validate();

        this._heuristics.improvePositioning(ranksBefore, rankYBefore);

        var movedNodes = this._findMovedNodes( numNodesBefore, positionsBefore, ranksBefore, vertLevelsBefore, rankYBefore );
        if (!arrayContains(movedNodes, parentRel))
            movedNodes.push(parentRel);
        var animateNodes = this.DG.GG.getInEdges(parentRel).slice(0);  
        animateNodes.push(personId);
        var newNodes   = [newNodeId];
        return {"new": newNodes, "moved": movedNodes, "animate": animateNodes};
    },

    removeNodes: function( nodeList )
    {
        this._debugPrintAll("before");
        var removed = nodeList.slice(0);
        removed.sort();
        var moved = [];

        for (var i = 0; i < nodeList.length; i++) {
            if (this.isRelationship(nodeList[i])) {
                
                var chHub = this.DG.GG.getOutEdges(nodeList[i])[0];
                nodeList.push(chHub);
                console.log("adding " + chHub + " to removal list (chhub of " + nodeList[i] + ")");

                var pathToParents = this.getPathToParents(nodeList[i]);
                for (var p = 0; p < pathToParents.length; p++) {
                    for (var j = 0; j < pathToParents[p].length; j++)
                        if (this.DG.GG.isVirtual(pathToParents[p][j])) {
                            console.log("adding " + pathToParents[p][j] + " to removal list (virtual of " + nodeList[i] + ")");
                            nodeList.push(pathToParents[p][j]);
                        }
                }
            }
        }

        nodeList.sort(function(a,b){return a-b});
        for (var i = nodeList.length-1; i >= 0; i--) {
            var v = nodeList[i];

            this.DG.GG.remove(v);
            //console.log("order before: " + stringifyObject(this.DG.order));
            this.DG.order.remove(v, this.DG.ranks[v]);
            //console.log("order after: " + stringifyObject(this.DG.order));
            this.DG.ranks.splice(v,1);
            this.DG.positions.splice(v, 1);
        }

        this.DG.maxRank = Math.max.apply(null, this.DG.ranks);

        this.DG.GG.validate();

        this.DG.vertLevel = this.DG.positionVertically();
        this.updateAncestors();

        for (var i = 0 ; i <= this.getMaxNodeId(); i++)
            if (this.isRelationship(i))
                moved.push(i);
        return {"removed": removed, "removedInternally": nodeList, "moved": moved };
    },

    improvePosition: function ()
    {
        var positionsBefore  = this.DG.positions.slice(0);
        var ranksBefore      = this.DG.ranks.slice(0);
        var vertLevelsBefore = this.DG.vertLevel.copy();
        var rankYBefore      = this.DG.rankY.slice(0);
        var numNodesBefore   = this.DG.GG.getMaxRealVertexId();

        this._heuristics.improvePositioning(ranksBefore, rankYBefore);

        var movedNodes = this._findMovedNodes( numNodesBefore, positionsBefore, ranksBefore, vertLevelsBefore, rankYBefore );

        return {"moved": movedNodes};
    },

    clearAll: function()
    {
        var removedNodes = this._getAllNodes(1);  

        var emptyGraph = (this.DG.GG.getNumVertices() == 0);

        var node0properties = emptyGraph ? {} : this.getProperties(0);


        var baseGraph = PedigreeImport.initFromPhenotipsInternal(this._onlyProbandGraph);

        this._recreateUsingBaseGraph(baseGraph);

        this.setProperties(0, node0properties);

        if (emptyGraph)
            return {"new": [0], "makevisible": [0]};

        return {"removed": removedNodes, "moved": [0], "makevisible": [0]};
    },

    redrawAll: function (animateList, newList, ranksBefore)
    {
        var ranksBefore = ranksBefore ? ranksBefore : this.DG.ranks.slice(0);  

        this._debugPrintAll("before");

        var baseGraph = this.DG.GG.makeGWithCollapsedMultiRankEdges();

        var oldRanks = clone2DArray(this.DG.order.order);
        for (var i = oldRanks.length - 1; i >=0; i--) {
            oldRanks[i] = oldRanks[i].filter(this.DG.GG.isPerson.bind(this.DG.GG));
            if (oldRanks[i].length == 0)
                oldRanks.splice(i, 1);
        }

        if (!this._recreateUsingBaseGraph(baseGraph, oldRanks)) return {};  

        var movedNodes = this._getAllNodes();

        var probandReRankSize = (ranksBefore[0] - this.DG.ranks[0]);
        var reRankedDiffFrom0 = []
        var reRanked          = [];
        for (var i = 0; i <= this.DG.GG.getMaxRealVertexId(); i++) {
            if (this.DG.GG.isPerson(i))
                if (this.DG.ranks[i] != ranksBefore[i]) {
                    reRanked.push(i);
                }
                if ((ranksBefore[i] - this.DG.ranks[i]) != probandReRankSize) {
                    reRankedDiffFrom0.push(i);
                }
        }
        if (reRankedDiffFrom0.length < reRanked.length) {
            reRanked = reRankedDiffFrom0;
        }

        if (!animateList) animateList = [];

        if (!newList)
            newList = [];
        else {
            for (var i = 0; i < newList.length; i++)
                removeFirstOccurrenceByValue(movedNodes, newList[i]);
        }

        this._debugPrintAll("after");

        return {"new": newList, "moved": movedNodes, "highlight": reRanked, "animate": animateList};
    },

    stripUnusedProperties: function() {
        for (var i = 0; i <= this.DG.GG.getMaxRealVertexId(); i++) {
            if (this.isPerson(i)) {
                this.deleteEmptyProperty(i, "fName");
                this.deleteEmptyProperty(i, "lName");
                this.deleteEmptyProperty(i, "gestationAge");
                this.deleteEmptyProperty(i, "carrierStatus");
                this.deleteEmptyProperty(i, "comments");
                this.deleteEmptyProperty(i, "disorders");
            }
         }
    },

    deleteEmptyProperty: function(nodeID, propName) {
        if (this.DG.GG.properties[nodeID].hasOwnProperty(propName)) {
            if (Object.prototype.toString.call(this.DG.GG.properties[nodeID][propName]) === '[object Array]' &&
                this.DG.GG.properties[nodeID][propName].length == 0) {
                delete this.DG.GG.properties[nodeID][propName];
            } else if (this.DG.GG.properties[nodeID][propName] == "") {
                delete this.DG.GG.properties[nodeID][propName];
            }
        }
    },

    toJSON: function ()
    {
        this.stripUnusedProperties();

        var output = {};

        output["GG"] = this.DG.GG.serialize();

        output["ranks"]     = this.DG.ranks;
        output["order"]     = this.DG.order.serialize();
        output["positions"] = this.DG.positions;


        //console.log("JSON represenation: " + JSON.stringify(output));

        return JSON.stringify(output);
    },

    fromJSON: function (serializedAsJSON)
    {
        var removedNodes = this._getAllNodes();

        var serializedData = JSON.parse(serializedAsJSON);


        this.DG.GG = PedigreeImport.initFromPhenotipsInternal(serializedData["GG"]);

        this.DG.ranks = serializedData["ranks"];

        this.DG.maxRank = Math.max.apply(null, this.DG.ranks);

        this.DG.order.deserialize(serializedData["order"]);

        this.DG.positions = serializedData["positions"];

        this._updateauxiliaryStructures();

        this.screenRankShift = 0;

        var newNodes = this._getAllNodes();

        return {"new": newNodes, "removed": removedNodes};
    },

    fromImport: function (importString, importType, importOptions)
    {
        var removedNodes = this._getAllNodes();


        if (importType == "ped") {
            var baseGraph = PedigreeImport.initFromPED(importString, importOptions.acceptUnknownPhenotypes, importOptions.markEvaluated, importOptions.externalIdMark);
            if (!this._recreateUsingBaseGraph(baseGraph)) return null;  // no changes
        } else if (importType == "BOADICEA") {
            var baseGraph = PedigreeImport.initFromBOADICEA(importString, importOptions.externalIdMark);
            if (!this._recreateUsingBaseGraph(baseGraph)) return null;  // no changes
        } else if (importType == "gedcom") {
            var baseGraph = PedigreeImport.initFromGEDCOM(importString, importOptions.markEvaluated, importOptions.externalIdMark);
            if (!this._recreateUsingBaseGraph(baseGraph)) return null;  // no changes
        } else if (importType == "simpleJSON") {
            var baseGraph = PedigreeImport.initFromSimpleJSON(importString);
            if (!this._recreateUsingBaseGraph(baseGraph)) return null;  // no changes
        }  else if (importType == "phenotipsJSON") {

            // TODO
        }


        var newNodes = this._getAllNodes();

        return {"new": newNodes, "removed": removedNodes};
    },

    getPathToParents: function(v)
    {
        return this.DG.GG.getPathToParents(v);
    },

    //=============================================================

    _recreateUsingBaseGraph: function (baseGraph, suggestedRanks)
    {
        try {
            var newDG = new PositionedGraph( baseGraph,
                                             this.DG.horizontalPersonSeparationDist,
                                             this.DG.horizontalRelSeparationDist,
                                             this.DG.maxInitOrderingBuckets,
                                             this.DG.maxOrderingIterations,
                                             this.DG.maxXcoordIterations,
                                             false,
                                             suggestedRanks );
        } catch (e) {
            return false;
        }

        this.DG          = newDG;
        this._heuristics = new Heuristics( this.DG );

        this._heuristics.improvePositioning();

        return true;
    },

    _insertVertex: function (type, properties, edgeWeights, inedge, outedge, insertRank, insertOrder)
    {
        if (inedge === null && outedge === null)
            throw "Assertion failed: each node should be connected to at least one other node";
        if (inedge !== null && outedge !== null)
            throw "Assertion failed: not clear which edge crossing to optimize, can only insert one edge";

        var inedges  = (inedge  !== null) ? [inedge]  : [];
        var outedges = (outedge !== null) ? [outedge] : [];

        var newNodeId = this.DG.GG.insertVertex(type, properties, edgeWeights, inedges, outedges);

        if (insertRank == 0) {
            for (var i = 0; i < this.DG.ranks.length; i++)
                this.DG.ranks[i]++;
            this.DG.maxRank++;

            this.DG.order.insertRank(1);

            insertRank = 1;
        }
        else if (insertRank > this.DG.maxRank) {
            this.DG.maxRank = insertRank;
            this.DG.order.insertRank(insertRank);
        }

        this.DG.ranks.splice(newNodeId, 0, insertRank);

        this.DG.order.insertAndShiftAllIdsAboveVByOne(newNodeId, insertRank, insertOrder);

        this.DG.positions.splice( newNodeId, 0, -Infinity ); 

        var nodeToKeepEdgeStraightTo = (inedge != null) ? inedge : outedge;
        this._heuristics.moveToCorrectPositionAndMoveOtherNodesAsNecessary( newNodeId, nodeToKeepEdgeStraightTo );

        return newNodeId;
    },

    _updateauxiliaryStructures: function(ranksBefore, rankYBefore)
    {
        var timer = new Timer();

        this.DG.vertLevel = this.DG.positionVertically();
        this.DG.rankY     = this.DG.computeRankY(ranksBefore, rankYBefore);

        this.updateAncestors();

        timer.printSinceLast("=== Vertical spacing + ancestors runtime: ");
    },

    _getAllNodes: function (minID, maxID)
    {
        var nodes = [];
        var minID = minID ? minID : 0;
        var maxID = maxID ? Math.min( maxID, this.DG.GG.getMaxRealVertexId()) : this.DG.GG.getMaxRealVertexId();
        for (var i = minID; i <= maxID; i++) {
            if ( this.DG.GG.type[i] == TYPE.PERSON || this.DG.GG.type[i] == TYPE.RELATIONSHIP )
                nodes.push(i);
        }
        return nodes;
    },

    _findMovedNodes: function (maxOldID, positionsBefore, ranksBefore, vertLevelsBefore, rankYBefore, consangrBefore)
    {

        var oldMin = Math.min.apply( Math, positionsBefore );
        var newMin = Math.min.apply( Math, this.DG.positions );
        if (newMin > oldMin) {
            var oldMinNodeID = arrayIndexOf(positionsBefore, oldMin);
            var newMinValue  = this.DG.positions[oldMinNodeID];
            var shiftAmount  = newMinValue - oldMin;

            for (var i = 0; i < this.DG.positions.length; i++)
                this.DG.positions[i] -= shiftAmount;
        }


        var result = {};
        for (var i = 0; i <= maxOldID; i++) {
            if (this.DG.GG.type[i] == TYPE.RELATIONSHIP || this.DG.GG.type[i] == TYPE.PERSON)
            {
                var rank = this.DG.ranks[i];
                if (rankYBefore && this.DG.rankY[rank] != rankYBefore[ranksBefore[i]]) {
                    this._addNodeAndAssociatedRelationships(i, result, maxOldID);
                    continue;
                }
                if (this.DG.positions[i] != positionsBefore[i]) {
                    this._addNodeAndAssociatedRelationships(i, result, maxOldID);
                    continue;
                }
                if (this.DG.GG.type[i] == TYPE.RELATIONSHIP) {
                    if (consangrBefore && !consangrBefore.hasOwnProperty(i) && this.DG.consangr.hasOwnProperty(i)) {
                        result[i] = true;
                        continue;
                    }
                    var inEdges = this.DG.GG.getInEdges(i);
                    if (inEdges[0] > this.DG.GG.maxRealVertexId || inEdges[1] > this.DG.GG.maxRealVertexId) {
                        result[i] = true;
                        continue;
                    }
                    var parents = this.DG.GG.getParents(i);
                    if (vertLevelsBefore.outEdgeVerticalLevel[parents[0]] !== undefined &&    // vertical levels may be outdated if multiple nodes were created in one batch
                        vertLevelsBefore.outEdgeVerticalLevel[parents[1]] !== undefined) {
                        if (vertLevelsBefore.outEdgeVerticalLevel[parents[0]][i].verticalLevel !=  this.DG.vertLevel.outEdgeVerticalLevel[parents[0]][i].verticalLevel ||
                            vertLevelsBefore.outEdgeVerticalLevel[parents[1]][i].verticalLevel !=  this.DG.vertLevel.outEdgeVerticalLevel[parents[1]][i].verticalLevel)
                        {
                            result[i] = true;
                            continue;
                        }
                    }

                    var childHub = this.DG.GG.getRelationshipChildhub(i);
                    if (vertLevelsBefore.childEdgeLevel[childHub] !== undefined && vertLevelsBefore.childEdgeLevel[childHub] != this.DG.vertLevel.childEdgeLevel[childHub]) {
                        result[i] = true;
                        continue;
                    }
                }
            }
        }

        var resultArray = [];
        for (var node in result) {
            if (result.hasOwnProperty(node)) {
                resultArray.push(parseInt(node));
            }
        }

        return resultArray;
    },

    _addNodeAndAssociatedRelationships: function ( node, addToSet, maxOldID )
    {
        addToSet[node] = true;
        if (this.DG.GG.type[node] != TYPE.PERSON) return;

        var inEdges = this.DG.GG.getInEdges(node);
        if (inEdges.length > 0) {
            var parentChildhub     = inEdges[0];
            var parentRelationship = this.DG.GG.getInEdges(parentChildhub)[0];
            if (parentRelationship <= maxOldID)
                addToSet[parentRelationship] = true;
        }

        var outEdges = this.DG.GG.getOutEdges(node);
        for (var i = 0; i < outEdges.length; i++) {
            if (outEdges[i] <= maxOldID)
                addToSet[ outEdges[i] ] = true;
        }
    },

    //=============================================================

    _addMultiRankEdge: function ( personId, relationshipId, _weight )
    {
        var weight = _weight ? _weight : 1.0;

        var rankPerson       = this.DG.ranks[personId];
        var rankRelationship = this.DG.ranks[relationshipId];

        if (rankPerson > rankRelationship - 2)
            throw "Assertion failed: attempt to make a multi-rank edge between non-multirank ranks";

        var otherpartner   = this.DG.GG.getInEdges(relationshipId)[0];

        var order_person   = this.DG.order.vOrder[personId];
        var order_rel      = this.DG.order.vOrder[relationshipId];

        var x_person       = this.DG.positions[otherpartner];
        var x_relationship = this.DG.positions[relationshipId];

        var prevPieceOrder = (x_person < x_relationship) ? (order_rel+1) : order_rel;
        var prevPieceId    = this._insertVertex(TYPE.VIRTUALEDGE, {}, weight, null, relationshipId, rankRelationship, prevPieceOrder);


        var rankNext = rankRelationship;
        while (--rankNext > rankPerson) {

            var prevNodeX = this.DG.positions[prevPieceId];
            var orderToMakeEdgeStraight = this.DG.order.order[rankNext].length;
            for (var o = 0; o < this.DG.order.order[rankNext].length; o++)
                if (this.DG.positions[this.DG.order.order[rankNext][o]] >= prevNodeX) {
                    orderToMakeEdgeStraight = o;
                    break;
                }

            console.log("adding piece @ rank: " + rankNext + " @ order " + orderToMakeEdgeStraight);

            prevPieceId = this._insertVertex(TYPE.VIRTUALEDGE, {}, weight, null, prevPieceId, rankNext, orderToMakeEdgeStraight);
        }

        this.DG.GG.addEdge(personId, prevPieceId, weight);
    },


    //=============================================================

    _findBestInsertPosition: function ( rank, edgeToV, preferLeft, _fromOrder, _toOrder )
    {

        if (rank == 0 || rank > this.DG.maxRank)
            return 0;

        var edgeToRank      = this.DG.ranks[ edgeToV ];
        var edgeToOrder     = this.DG.order.vOrder[edgeToV];

        if (edgeToRank == rank && this.isPerson(edgeToV))
            return this._findBestRelationshipPosition( edgeToV, preferLeft );

        var bestInsertOrder  = 0;
        var bestCrossings    = Infinity;
        var bestDistance     = Infinity;

        var crossingChildhubEdgesPenalty = false;
        if (this.DG.GG.type[edgeToV] == TYPE.CHILDHUB)
            crossingChildhubEdgesPenalty = true;

        var desiredOrder = 0;

        var edgeToX = this.DG.positions[edgeToV];
        for (var o = 0; o < this.DG.order.order[rank].length; o++) {
            var uAtPos = this.DG.order.order[rank][o];
            var uX     = this.DG.positions[uAtPos];
            if (uX < edgeToX) {
                desiredOrder = o+1;
            }
            else {
                break;
            }
        }

        if (this.DG.GG.type[edgeToV] == TYPE.CHILDHUB && rank > edgeToRank && this.DG.GG.getOutEdges(edgeToV).length > 0)
            desiredOrder = this._findRightmostChildPosition(edgeToV) + 1;

        var fromOrder = _fromOrder ? Math.max(_fromOrder,0) : 0;
        var toOrder   = _toOrder   ? Math.min(_toOrder,this.DG.order.order[rank].length) : this.DG.order.order[rank].length;
        for (var o = fromOrder; o <= toOrder; o++) {

            if (o > 0 && o < this.DG.order.order[rank].length) {
                var leftNodePos = o-1;
                while (leftNodePos > 0 && this.DG.GG.isVirtual(this.DG.order.order[rank][leftNodePos]))
                    leftNodePos--;
                rightNodePos = o;
                while (rightNodePos < this.DG.order.order[rank].length-1 && this.DG.GG.isVirtual(this.DG.order.order[rank][rightNodePos]))
                    rightNodePos--;
                var nodeToTheLeft  = this.DG.order.order[rank][leftNodePos];
                var nodeToTheRight = this.DG.order.order[rank][rightNodePos];

                if (this.isPerson(nodeToTheLeft) && this.isPerson(nodeToTheRight)) {
                    var rel1 = this.DG.GG.getProducingRelationship(nodeToTheLeft);
                    var rel2 = this.DG.GG.getProducingRelationship(nodeToTheRight);
                    if (rel1 == rel2) {
                        var twinGroupId1 = this.DG.GG.getTwinGroupId(nodeToTheLeft);
                        var twinGroupId2 = this.DG.GG.getTwinGroupId(nodeToTheRight);
                        if (twinGroupId1 !== null && twinGroupId1 == twinGroupId2)
                            continue;
                    }
                }
            }

            var numCrossings = this._edgeCrossingsByFutureEdge( rank, o - 0.5, edgeToRank, edgeToOrder, crossingChildhubEdgesPenalty, edgeToV );

            if ( numCrossings < bestCrossings ||                           // less crossings
                 (numCrossings == bestCrossings && Math.abs(o - desiredOrder) <= bestDistance )   // closer to desired position
               ) {
               bestInsertOrder = o;
               bestCrossings   = numCrossings;
               bestDistance    = Math.abs(o - desiredOrder);
            }
        }

        return bestInsertOrder;
    },

    _findRightmostChildPosition: function ( vertex )
    {
        var childrenInfo = this._heuristics.analizeChildren(vertex);
        return childrenInfo.rightMostChildOrder;
    },

    _edgeCrossingsByFutureEdge: function ( newVRank, newVOrder, existingURank, existingUOrder, crossingChildhubEdgesPenalty, existingU )
    {
        var rankFrom  = Math.min( newVRank, existingURank );
        var rankTo    = Math.max( newVRank, existingURank );
        var orderFrom = (newVRank < existingURank) ? newVOrder : existingUOrder;
        var orderTo   = (newVRank < existingURank) ? existingUOrder : newVOrder;

        var vSibglingInfo = undefined;
        if (this.DG.GG.isChildhub(existingU) && (newVRank > existingURank) &&
            this.DG.GG.getOutEdges(existingU).length > 0) {
            vSibglingInfo = this._heuristics.analizeChildren(existingU);

            if (vSibglingInfo.numWithTwoPartners < vSibglingInfo.orderedChildren.length) {
                var okPosition = false;
                if (newVOrder > 0) {                                        
                    var leftNeighbour = this.DG.order.order[newVRank][ Math.floor(newVOrder)];
                    var neighbourInEdges = this.DG.GG.getInEdges(leftNeighbour);
                    if (neighbourInEdges.length == 1 && neighbourInEdges[0] == existingU) {
                        okPosition = true;  
                    }
                }
                if (newVOrder < this.DG.order.order[newVRank].length - 1) {  
                    var rightNeighbour = this.DG.order.order[newVRank][ Math.ceil(newVOrder)];
                    var neighbourInEdges = this.DG.GG.getInEdges(rightNeighbour);
                    if (neighbourInEdges.length == 1 && neighbourInEdges[0] == existingU) {
                        okPosition = true;  
                    }
                }
                if (!okPosition) {
                    return Infinity;
                }
            }
        }

        var crossings = 0;

        if (rankFrom == rankTo) throw "TODO: probably not needed";


        var verticesAtRankTo = this.DG.order.order[ rankTo ];

        for (var ord = 0; ord < verticesAtRankTo.length; ord++) {
            if ( ord == orderTo ) continue;

            var vertex = verticesAtRankTo[ord];

            var inEdges = this.DG.GG.getInEdges(vertex);
            var len     = inEdges.length;

            for (var j = 0; j < len; j++) {
                var target = inEdges[j];

                var penalty = 1;
                if (crossingChildhubEdgesPenalty && this.DG.GG.isChildhub(target)) {
                    penalty = 100000;
                    if (vSibglingInfo) {
                        var targetChildren = this._heuristics.analizeChildren(target);

                        if (targetChildren.leftMostChildOrder < vSibglingInfo.rightMostChildOrder &&
                            targetChildren.rightMostChildOrder > vSibglingInfo.leftMostChildOrder) {
                            penalty = 1;
                        }
                    }
                }

                var orderTarget = this.DG.order.vOrder[target];
                var rankTarget  = this.DG.ranks[target];

                if (rankTarget == rankTo)
                {
                    if ( ord < orderTo && orderTarget > orderTo ||
                         ord > orderTo && orderTarget < orderTo )
                         crossings += 2;
                }
                else
                {
                    if (ord < orderTo && orderTarget > orderFrom ||
                        ord > orderTo && orderTarget < orderFrom )
                        crossings += penalty;
                }
            }
        }

        var verticesAtNewRank = this.DG.order.order[ newVRank ];
        for (var ord = 0; ord < verticesAtNewRank.length; ord++) {
            if ( ord == newVOrder ) continue;

            var vertex = verticesAtNewRank[ord];

            var outEdges = this.DG.GG.getOutEdges(vertex);
            var len      = outEdges.length;

            for (var j = 0; j < len; j++) {
                var target = outEdges[j];

                var orderTarget = this.DG.order.vOrder[target];
                var rankTarget  = this.DG.ranks[target];

                if (rankTarget == newVRank)
                {
                    if ( newVOrder < ord && newVOrder > orderTarget ||
                         newVOrder > ord && newVOrder < orderTarget )
                         crossings += 0.1;
                }
            }
        }


        return crossings;
    },

    _findBestRelationshipPosition: function ( v, preferLeft, u )
    {

        var rank   = this.DG.ranks[v];
        var orderR = this.DG.order.order[rank];
        var isTwin = (this.DG.GG.getTwinGroupId(v) != null);
        var vOrder = this.DG.order.vOrder[v];

        var penaltyBelow    = [];
        var penaltySameRank = [];
        for (var o = 0; o <= orderR.length; o++) {
            penaltyBelow[o]    = 0;
            penaltySameRank[o] = 0;
        }

        for (var o = 0; o < orderR.length; o++) {
            var node = orderR[o];
            if (!this.isRelationship(node)) continue;
            var childrenInfo = this._heuristics.analizeChildren(node);

            if (childrenInfo.leftMostHasLParner)  { penaltyBelow[o]   += 1; penaltyBelow[o-1] += 0.25; }   // 0.25 is just a heuristic estimation of how busy the level below is.
            if (childrenInfo.rightMostHasRParner) { penaltyBelow[o+1] += 1; penaltyBelow[o+2] += 0.25; }
        }

        for (var o = 0; o < orderR.length; o++) {
            var node = orderR[o];
            if (!this.isRelationship(node)) continue;

            var relOrder = this.DG.order.vOrder[node];

            var parents = this.DG.GG.getInEdges(node);

            for (var p = 0; p < parents.length; p++) {
                var parent = parents[p];
                if (parent != v && this.DG.ranks[parent] == rank && parent != u) {
                    var parentOrder = this.DG.order.vOrder[parent];

                    var from = (parentOrder > relOrder) ? relOrder + 1 : parentOrder + 1;
                    var to   = (parentOrder > relOrder) ? parentOrder : relOrder;
                    for (var j = from; j <= to; j++)
                        penaltySameRank[j] = Infinity;
                }
            }
        }

        for (var o = 0; o < orderR.length; o++) {
            if (o == vOrder) continue;

            var node = orderR[o];
            if (!this.isPerson(node)) continue;
            var allTwins = this.getAllTwinsSortedByOrder(node);

            if (allTwins.length > 1) {
                var leftMostTwinOrder  = this.DG.order.vOrder[ allTwins[0] ];
                var rightMostTwinOrder = this.DG.order.vOrder[ allTwins[allTwins.length-1] ];
                for (var j = leftMostTwinOrder+1; j <= rightMostTwinOrder; j++)
                    penaltySameRank[j] = Infinity;
                o = rightMostTwinOrder; 
            }

            if (this.DG.GG.getProducingRelationship(node) != null) {
                if (o < vOrder) {
                    for (var j = 0; j <= o; j++)
                        penaltySameRank[j]++;
                }
                else {
                    for (var j = o+1; j <= orderR.length; j++)
                        penaltySameRank[j]++;
                }
            }
        }

        console.log("Insertion same rank penalties: " + stringifyObject(penaltySameRank));
        console.log("Insertion below penalties:     " + stringifyObject(penaltyBelow));

        if (u === undefined) {
            if (preferLeft && vOrder == 0) return 0;

            var partnerInfo = this.DG._findLeftAndRightPartners(v);
            var numLeftOf   = partnerInfo.leftPartners.length;
            var numRightOf  = partnerInfo.rightPartners.length;


            console.log("v: " + v + ", vOrder: " + vOrder + ", numL: " + numLeftOf + ", numR: " + numRightOf);

            if (!isTwin && numLeftOf  == 0 && (preferLeft || numRightOf > 0) ) return vOrder;
            if (!isTwin && numRightOf == 0 )                                   return vOrder + 1;

            var bestPosition = vOrder + 1;
            var bestPenalty  = Infinity;
            for (var o = 0; o <= orderR.length; o++) {
                var penalty = penaltyBelow[o] + penaltySameRank[o];
                if (o <= vOrder) {
                    penalty += numLeftOf + (vOrder - o);        
                    if (preferLeft)
                        penalty -= 0.5;   
                    else
                        penalty += 0.5;   //
                }
                else {
                    penalty += numRightOf + (o - vOrder - 1);   
                }

                if (penalty < bestPenalty) {
                    bestPenalty  = penalty;
                    bestPosition = o;
                }
            }
            return bestPosition;
        }

        if (this.DG.order.vOrder[v] > this.DG.order.vOrder[u]) {
            var tmp = u;
            u       = v;
            v       = tmp;
        }

        var orderV = this.DG.order.vOrder[v];
        var orderU = this.DG.order.vOrder[u];

        var partnerInfoV = this.DG._findLeftAndRightPartners(v);
        var numRightOf  = partnerInfoV.rightPartners.length;
        var partnerInfoU = this.DG._findLeftAndRightPartners(u);
        var numLeftOf   = partnerInfoU.leftPartners.length;

        if (numRightOf == 0 && numLeftOf > 0)  return orderV + 1;
        if (numRightOf > 0  && numLeftOf == 0) return orderU;

        var bestPosition = orderV + 1;
        var bestPenalty  = Infinity;
        for (var o = orderV+1; o <= orderU; o++) {
            var penalty = penaltyBelow[o] + penaltySameRank[o];

            for (var p = 0; p < partnerInfoV.rightPartners.length; p++) {
                var partner = partnerInfoV.rightPartners[p];
                if (o <= this.DG.order.vOrder[partner]) penalty++;
            }
            for (var p = 0; p < partnerInfoU.leftPartners.length; p++) {
                var partner = partnerInfoU.leftPartners[p];
                if (o > this.DG.order.vOrder[partner]) penalty++;
            }


            if (penalty <= bestPenalty) {
                bestPenalty  = penalty;
                bestPosition = o;
            }
        }
        return bestPosition;
    },

    //=============================================================

    _getAllPersonsOfGenders: function (validGendersSet)
    {

        for (var i = 0; i < validGendersSet.length; i++) {
            validGendersSet[i] = validGendersSet[i].toLowerCase();
            if (validGendersSet[i] != 'u' && validGendersSet[i] != 'm' && validGendersSet[i] != 'f')
                throw "Invalid gender: " + validGendersSet[i];
        }

         var result = [];

         for (var i = 0; i <= this.DG.GG.getMaxRealVertexId(); i++) {
            if (!this.isPerson(i)) continue;
            if (this.isPersonGroup(i)) continue;
            var gender = this.getProperties(i)["gender"].toLowerCase();
            if (arrayContains(validGendersSet, gender))
                result.push(i);
         }

         return result;
    }
};


Heuristics = function( drawGraph )
{
    this.DG = drawGraph;
};

Heuristics.prototype = {

    swapPartnerToBringToSideIfPossible: function ( personId )
    {

        if (this.DG.GG.getTwinGroupId(personId) !== null) return; 

        var rank  = this.DG.ranks[personId];
        var order = this.DG.order.vOrder[personId];

        if (order == 0 || order == this.DG.order.order[rank].length - 1) return; 

        var parnetships = this.DG.GG.getAllRelationships(personId);
        if (parnetships.length != 1) return;    
        var relationship = parnetships[0];
        var relOrder     = this.DG.order.vOrder[relationship];

        var partners  = this.DG.GG.getParents(relationship);
        var partnerId = (partners[0] == personId) ? partners[1] : partners[0];  
        var parnerOutEdges = this.DG.GG.getOutEdges(partnerId);
        if (parnerOutEdges.length != 1) return;  

        if (this.DG.ranks[personId] != this.DG.ranks[partnerId]) return; 

        var partnerOrder = this.DG.order.vOrder[partnerId];
        if (partnerOrder != order - 2 && partnerOrder != order + 2) return;  

        if (this.DG.GG.getInEdges(personId).length != 0 &&
            this.DG.GG.getInEdges(partnerId).length != 0 ) return;

        var childhubId = this.DG.GG.getOutEdges(relationship)[0]; 
        var children   = this.DG.GG.getOutEdges(childhubId);

        if (children.length == 0) return;



        var toTheLeft = (order < partnerOrder);

        var childrenPartners = this.analizeChildren(childhubId);

        if ( (toTheLeft  && childrenPartners.leftMostHasLParner  && !childrenPartners.rightMostHasRParner) ||
             (!toTheLeft && childrenPartners.rightMostHasRParner && !childrenPartners.leftMostHasLParner) ||
             (order == 2 && childrenPartners.rightMostHasRParner) ||
             (order == this.DG.order.order[rank].length - 3 && childrenPartners.leftMostHasLParner) ) {
            this.swapPartners( personId, partnerId, relationship );  
        }
    },

    swapTwinsToBringToSideIfPossible: function( personId )
    {
        var twinGroupId = this.DG.GG.getTwinGroupId(personId);
        if (twinGroupId === null) return;

        //TODO
    },

    analizeChildren: function (childhubId)
    {
        if (this.DG.GG.isRelationship(childhubId))
            childhubId = this.DG.GG.getOutEdges(childhubId)[0];

        if (!this.DG.GG.isChildhub(childhubId))
            throw "Assertion failed: applying analizeChildren() not to a childhub";

        var children = this.DG.GG.getOutEdges(childhubId);

        if (children.length == 0) return;

        var havePartners        = {};
        var numWithPartners     = 0;
        var numWithTwoPartners  = 0;
        var leftMostChildId     = undefined;
        var leftMostChildOrder  = Infinity;
        var leftMostHasLParner  = false;
        var rightMostChildId    = undefined;
        var rightMostChildOrder = -Infinity;
        var rightMostHasRParner = false;
        for (var i = 0; i < children.length; i++) {
            var childId = children[i];
            var order   = this.DG.order.vOrder[childId];

            if (order < leftMostChildOrder) {
                leftMostChildId    = childId;
                leftMostChildOrder = order;
                leftMostHasLParner = this.hasParnerBetweenOrders(childId, 0, order-1);  // has partner to the left
            }
            if (order > rightMostChildOrder) {
                rightMostChildId    = childId;
                rightMostChildOrder = order;
                rightMostHasRParner = this.hasParnerBetweenOrders(childId, order+1, Infinity);  // has partner to the right
            }
            if (this.DG.GG.getOutEdges(childId).length > 0) {
                havePartners[childId] = true;
                numWithPartners++;
                if (this.DG.GG.getOutEdges(childId).length > 1) {
                    numWithTwoPartners++;
                }
            }
        }

        var orderedChildren = this.DG.order.sortByOrder(children);
        //console.log("ordered ch: " + stringifyObject(orderedChildren));

        return {"leftMostHasLParner" : leftMostHasLParner,
                "leftMostChildId"    : leftMostChildId,
                "leftMostChildOrder" : leftMostChildOrder,
                "rightMostHasRParner": rightMostHasRParner,
                "rightMostChildId"   : rightMostChildId,
                "rightMostChildOrder": rightMostChildOrder,
                "withPartnerSet"     : havePartners,
                "numWithPartners"    : numWithPartners,
                "numWithTwoPartners" : numWithTwoPartners,
                "orderedChildren"    : orderedChildren };
    },

    hasParnerBetweenOrders: function( personId, minOrder, maxOrder )
    {
        var rank  = this.DG.ranks[personId];
        var order = this.DG.order.vOrder[personId];

        var outEdges = this.DG.GG.getOutEdges(personId);

        for (var i = 0; i < outEdges.length; i++ ) {
            var relationship = outEdges[i];
            var relRank      = this.DG.ranks[relationship];
            if (relRank != rank) continue;

            var relOrder = this.DG.order.vOrder[relationship];
            if (relOrder >= minOrder && relOrder <= maxOrder)
                return true;
        }

        return false;
    },

    swapPartners: function( partner1, partner2, relationshipId)
    {
        var rank = this.DG.ranks[partner1];
        if (this.DG.ranks[partner2] != rank || this.DG.ranks[relationshipId] != rank)
            throw "Assertion failed: swapping nodes of different ranks";

        var order1   = this.DG.order.vOrder[partner1];
        var order2   = this.DG.order.vOrder[partner2];
        var orderRel = this.DG.order.vOrder[relationshipId];

        if (order1 > order2) {
            var tmpOrder = order1;
            var tmpId    = partner1;
            order1   = order2;
            partner1 = partner2;
            order2   = tmpOrder;
            partner2 = tmpId;
        }

        if ( (order1 + 1) != orderRel || (orderRel + 1) != order2 ) return;

        this.DG.order.exchange(rank, order1, order2);

        var widthDecrease = this.DG.GG.getVertexWidth(partner1) - this.DG.GG.getVertexWidth(partner2);

        var pos2 = this.DG.positions[partner2];
        this.DG.positions[partner2] = this.DG.positions[partner1];
        this.DG.positions[partner1] = pos2 - widthDecrease;
        this.DG.positions[relationshipId] -= widthDecrease;
    },

    moveSiblingPlusPartnerToOrder: function ( personId, partnerId, partnershipId, newOrder)
    {

        var rank         = this.DG.ranks[partnerId];
        var partnerOrder = this.DG.order.vOrder[partnerId];
        var personOrder  = this.DG.order.vOrder[personId];
        var relOrder     = this.DG.order.vOrder[partnershipId];

        var moveOrders = newOrder - personOrder;

        var moveDistance  = this.DG.positions[this.DG.order.order[rank][newOrder]] - this.DG.positions[personId];

        var moveRight     = (newOrder > personOrder);
        var firstSibling  = moveRight ? this.DG.order.order[rank][personOrder + 1] : this.DG.order.order[rank][personOrder - 1];
        var moveOtherDist = this.DG.positions[firstSibling] - this.DG.positions[partnerId];


        this.DG.order.move(rank, personOrder,  moveOrders);
        this.DG.order.move(rank, relOrder,     moveOrders);
        this.DG.order.move(rank, partnerOrder, moveOrders);


        this.DG.positions[personId]      += moveDistance;
        this.DG.positions[partnerId]     += moveDistance;
        this.DG.positions[partnershipId] += moveDistance;

        var minMovedOrder = moveRight ?  partnerOrder : newOrder + 3;
        var maxMovedOrder = moveRight ?  newOrder - 3 : partnerOrder;
        for (var o = minMovedOrder; o <= maxMovedOrder; o++) {
            var node = this.DG.order.order[rank][o];
            console.log("moving: " + node);
            this.DG.positions[node] -= moveOtherDist;
        }
    },

    swapBeforeParentsToBringToSideIfPossible: function ( personId )
    {

        var parnetships = this.DG.GG.getAllRelationships(personId);
        if (parnetships.length != 1) return;
        var relationshipId = parnetships[0];

        var partners  = this.DG.GG.getParents(relationshipId);
        var partnerId = (partners[0] == personId) ? partners[1] : partners[0];  
        if (this.DG.GG.getInEdges(partnerId).length == 0) return; 

        if (this.DG.ranks[personId] != this.DG.ranks[partnerId]) return; 

        if (this.DG.GG.getOutEdges(partnerId).length > 1) return; 

        var order        = this.DG.order.vOrder[personId];
        var partnerOrder = this.DG.order.vOrder[partnerId];
        if (partnerOrder != order - 2 && partnerOrder != order + 2) return;  

        var toTheLeft = (order < partnerOrder);

        var partnerChildhubId   = this.DG.GG.getInEdges(partnerId)[0];
        var partnerSibglingInfo = this.analizeChildren(partnerChildhubId);

        if (partnerSibglingInfo.orderedChildren.length > 1) {
            if (partnerSibglingInfo.leftMostChildId == partnerId) {
                if (!toTheLeft)
                    this.swapPartners( personId, partnerId, relationshipId );
                return;
            }
            if (partnerSibglingInfo.rightMostChildId == partnerId) {
                if (toTheLeft)
                    this.swapPartners( personId, partnerId, relationshipId );
                return;
            }
        }

        var partnerParents = this.DG.GG.getInEdges(this.DG.GG.getInEdges(partnerChildhubId)[0]);
        var order0 = this.DG.order.vOrder[partnerParents[0]];
        var order1 = this.DG.order.vOrder[partnerParents[1]];
        var leftParent  = (order0 > order1) ? partnerParents[1] : partnerParents[0];
        var rightParent = (order0 > order1) ? partnerParents[0] : partnerParents[1];
        console.log("parents: " + stringifyObject(partnerParents));
        var numLeftPartners  = this.DG.GG.getOutEdges(leftParent).length;
        var numRightPartners = this.DG.GG.getOutEdges(rightParent).length;
        console.log("num left: " + numLeftPartners + ", numRight: " + numRightPartners);
        if (numLeftPartners > 1 && numRightPartners > 1) return;

        if (partnerSibglingInfo.orderedChildren.length == 1) {
            if (numLeftPartners == 1 && numRightPartners == 1) {
                return;
            }
            if (numLeftPartners == 1 && !toTheLeft) {
                this.swapPartners( personId, partnerId, relationshipId );
            }
            if (numRightPartners == 1 && toTheLeft) {
                this.swapPartners( personId, partnerId, relationshipId );
            }
            return; 
        }

        var childHubBelow = this.DG.GG.getRelationshipChildhub(relationshipId);
        var childrenInfo  = this.analizeChildren(childHubBelow);
        if (childrenInfo.numWithPartners > 0) return;  

        if (numRightPartners == 1 && !partnerSibglingInfo.rightMostHasRParner) {
            for (var c = partnerSibglingInfo.orderedChildren.length - 1; c >= 0; c--) {
                var sibling = partnerSibglingInfo.orderedChildren[c];
                if (sibling == partnerId) {
                    if (toTheLeft)
                        this.swapPartners( personId, partnerId, relationshipId );
                    this.moveSiblingPlusPartnerToOrder( personId, partnerId, relationshipId, partnerSibglingInfo.rightMostChildOrder);
                    return;
                }
                if (partnerSibglingInfo.withPartnerSet.hasOwnProperty(sibling)) break; 
            }
        }
        if (numLeftPartners == 1 && !partnerSibglingInfo.leftMostHasLParner) {
            for (var c = 0; c < partnerSibglingInfo.orderedChildren.length; c++) {
                var sibling = partnerSibglingInfo.orderedChildren[c];
                if (sibling == partnerId) {
                    if (!toTheLeft)
                        this.swapPartners( personId, partnerId, relationshipId );
                    this.moveSiblingPlusPartnerToOrder( personId, partnerId, relationshipId, partnerSibglingInfo.leftMostChildOrder);
                    return;
                }
                if (partnerSibglingInfo.withPartnerSet.hasOwnProperty(sibling)) break; // does not work on this side
            }
        }
    },

    improvePositioning: function (ranksBefore, rankYBefore)
    {
        var timer = new Timer();

        var modified = false;
        for (var parent = 0; parent <= this.DG.GG.getMaxRealVertexId(); parent++) {
            if (!this.DG.GG.isPerson(parent)) continue;

            var rank  = this.DG.ranks[parent];
            var order = this.DG.order.vOrder[parent];

            var outEdges = this.DG.GG.getOutEdges(parent);

            var sameRankToTheLeft  = 0;
            var sameRankToTheRight = 0;

            var multiRankEdges = [];
            for (var i = 0; i < outEdges.length; i++) {
                var node = outEdges[i];
                if (this.DG.ranks[node] != rank)
                    multiRankEdges.push(node);
                else {
                    if (this.DG.order.vOrder[node] < order)
                        sameRankToTheLeft++;
                    else
                        sameRankToTheRight++;
                }
            }
            if (multiRankEdges.length == 0) continue;

            var _this = this;
            byXcoord = function(v1,v2) {
                    var rel1      = _this.DG.GG.downTheChainUntilNonVirtual(v1);
                    var rel2      = _this.DG.GG.downTheChainUntilNonVirtual(v2);
                    var position1 = _this.DG.positions[rel1];
                    var position2 = _this.DG.positions[rel2];
                    var parentPos = _this.DG.positions[parent];
                    if (position1 >= parentPos && position2 >= parentPos)
                        return position1 < position2;
                    else
                        return position1 > position2;
                };
            multiRankEdges.sort(byXcoord);

            console.log("multi-rank edges: " + stringifyObject(multiRankEdges));

            for (var p = 0; p < multiRankEdges.length; p++) {

                var firstOnPath = multiRankEdges[p];

                var relNode = this.DG.GG.downTheChainUntilNonVirtual(firstOnPath);

                var weight = this.DG.GG.removeEdge(parent, firstOnPath);

                var newNodeId = this.DG.GG.insertVertex(TYPE.VIRTUALEDGE, {}, weight, [parent], [firstOnPath]);

                this.DG.ranks.splice(newNodeId, 0, rank);

                var insertToTheRight = (this.DG.positions[relNode] < this.DG.positions[parent]) ? false : true;

                if (this.DG.positions[relNode] == this.DG.positions[parent]) {
                    if (sameRankToTheRight > 0 && sameRankToTheLeft == 0 && multiRankEdges.length == 1) {
                        insertToTheRight = false;  
                    }
                }


                var parentOrder = this.DG.order.vOrder[parent]; 

                var newOrder = insertToTheRight ? parentOrder + 1 : parentOrder;
                if (insertToTheRight) {
                    while (newOrder < this.DG.order.order[rank].length &&
                           this.DG.positions[firstOnPath] > this.DG.positions[ this.DG.order.order[rank][newOrder] ])
                        newOrder++;

                    var toTheLeft  = this.DG.order.order[rank][newOrder-1];
                    var toTheRight = this.DG.order.order[rank][newOrder];
                    if (this.DG.GG.isRelationship(toTheLeft) && this.DG.GG.isPerson(toTheRight) &&
                        this.DG.GG.hasEdge(toTheRight, toTheLeft) && this.DG.GG.getOutEdges(toTheRight).length ==1 )
                        newOrder++;
                    if (this.DG.GG.isRelationship(toTheRight) && this.DG.GG.isPerson(toTheLeft) &&
                        this.DG.GG.hasEdge(toTheLeft, toTheRight) && this.DG.GG.getOutEdges(toTheLeft).length ==1 )
                        newOrder--;
                }
                else {
                    while (newOrder > 0 &&
                           this.DG.positions[firstOnPath] < this.DG.positions[ this.DG.order.order[rank][newOrder-1] ])
                        newOrder--;

                    var toTheLeft  = this.DG.order.order[rank][newOrder-1];
                    var toTheRight = this.DG.order.order[rank][newOrder];
                    if (this.DG.GG.isRelationship(toTheRight) && this.DG.GG.isPerson(toTheLeft) &&
                        this.DG.GG.hasEdge(toTheLeft, toTheRight) && this.DG.GG.getOutEdges(toTheLeft).length ==1 )
                        newOrder--;
                    if (this.DG.GG.isRelationship(toTheLeft) && this.DG.GG.isPerson(toTheRight) &&
                        this.DG.GG.hasEdge(toTheRight, toTheLeft) && this.DG.GG.getOutEdges(toTheRight).length ==1 )
                        newOrder++;
                }

                this.DG.order.insertAndShiftAllIdsAboveVByOne(newNodeId, rank, newOrder);

                this.DG.positions.splice( newNodeId, 0, -Infinity ); 

                var nodeToKeepEdgeStraightTo = firstOnPath;
                this.moveToCorrectPositionAndMoveOtherNodesAsNecessary( newNodeId, nodeToKeepEdgeStraightTo );

                modified = true;
            }
        }

        this.optimizeLongEdgePlacement();

        timer.printSinceLast("=== Long edge handling runtime: ");

        var xcoord = new XCoord(this.DG.positions, this.DG);

        for (var v = 0; v <= this.DG.GG.getMaxRealVertexId(); v++) {
            if (!this.DG.GG.isRelationship(v)) continue;
            var childhub  = this.DG.GG.getRelationshipChildhub(v);
            var relX      = xcoord.xcoord[v];
            var childhubX = xcoord.xcoord[childhub];
            if (childhubX != relX) {
                improved  = xcoord.moveNodeAsCloseToXAsPossible(childhub, relX);
            }
        }

        for (var v = 0; v <= this.DG.GG.getMaxRealVertexId(); v++) {
            if (!this.DG.GG.isChildhub(v)) continue;
            var children = this.DG.GG.getOutEdges(v);
            if (children.length < 2) continue;

            var orderedChildren = this.DG.order.sortByOrder(children);

            for (var i = orderedChildren.length-1; i >= 0; i--) {
                if (i == 0 || this.DG.GG.getOutEdges(orderedChildren[i]).length > 0) {
                    for (var j = i+1; j < orderedChildren.length; j++) {
                        xcoord.shiftLeftOneVertex(orderedChildren[j], Infinity);
                    }
                    break;
                }
            }
            for (var i = 0; i < orderedChildren.length; i++) {
                if (i == (orderedChildren.length-1) || this.DG.GG.getOutEdges(orderedChildren[i]).length > 0) {
                    for (var j = i-1; j >= 0; j--) {
                        xcoord.shiftRightOneVertex(orderedChildren[j], Infinity);
                    }
                    break;
                }
            }
        }


        this._compactGraph(xcoord, 5);


        var orderedRelationships = this.DG.order.getLeftToRightTopToBottomOrdering(TYPE.RELATIONSHIP, this.DG.GG);

        var iter = 0;
        var improved = true;
        while (improved && iter < 20)
        {
            improved = false;
            iter++;

            for (var k = 0; k < orderedRelationships.length; k++) {
                var v = orderedRelationships[k];

                var parents   = this.DG.GG.getInEdges(v);
                var childhub  = this.DG.GG.getRelationshipChildhub(v);

                var relX      = xcoord.xcoord[v];
                var childhubX = xcoord.xcoord[childhub];

                var childInfo = this.analizeChildren(childhub);

                var misalignment = 0;

                if (childInfo.orderedChildren.length == 1) {
                    var childId = childInfo.orderedChildren[0];
                    if (xcoord.xcoord[childId] == childhubX) continue;

                    improved = xcoord.moveNodeAsCloseToXAsPossible(childId, childhubX);

                    if (xcoord.xcoord[childId] == childhubX) continue; 

                    misalignment = xcoord.xcoord[childId] - childhubX;
                }
                else {
                    var positionInfo = this._computeDesiredChildhubLocation( childInfo, xcoord );

                    if (positionInfo.minPreferred <= childhubX && childhubX <= positionInfo.maxPreferred) continue;

                    var shiftToX = (childhubX > positionInfo.maxPreferred) ? positionInfo.maxPreferred : positionInfo.minPreferred;

                    var needToShift = childhubX - shiftToX;

                    if (childInfo.numWithPartners == 0) {
                        if (needToShift < 0) { 
                            var leftMost  = childInfo.leftMostChildId;
                            var leftSlack = xcoord.getSlackOnTheLeft(leftMost);
                            var haveSlack = Math.min(Math.abs(needToShift), leftSlack);
                            if (haveSlack > 0) {
                                for (var i = 0; i < childInfo.orderedChildren.length; i++)
                                    xcoord.xcoord[childInfo.orderedChildren[i]] -= haveSlack;
                                improved = true;
                                needToShift += haveSlack;
                            }
                        }
                        else {  
                            var rightMost  = childInfo.rightMostChildId;
                            var rightSlack = xcoord.getSlackOnTheRight(rightMost);
                            var haveSlack = Math.min(needToShift, rightSlack);
                            if (haveSlack > 0) {
                                for (var i = 0; i < childInfo.orderedChildren.length; i++)
                                    xcoord.xcoord[childInfo.orderedChildren[i]] += haveSlack;
                                improved = true;
                                needToShift -= haveSlack;
                            }
                        }
                    }
                    misalignment = -needToShift;
                }

                if (misalignment == 0) continue;


                var leftParent  = (xcoord.xcoord[parents[0]] < xcoord.xcoord[parents[1]]) ? parents[0] : parents[1];
                var rightParent = (xcoord.xcoord[parents[0]] < xcoord.xcoord[parents[1]]) ? parents[1] : parents[0];

                var shiftList = [v, childhub];
                if (this.DG.order.vOrder[leftParent]  == this.DG.order.vOrder[v] - 1 && !this.DG.GG.isVirtual(leftParent)) {
                    if (misalignment > 0 || xcoord.getSlackOnTheLeft(v) < -misalignment)
                        shiftList.unshift(leftParent);
                }
                if (this.DG.order.vOrder[rightParent] == this.DG.order.vOrder[v] + 1 && !this.DG.GG.isVirtual(rightParent)) {
                    if (misalignment < 0 || xcoord.getSlackOnTheRight(v) < misalignment)
                        shiftList.push(rightParent);
                }
                var noUpSet = {};
                noUpSet[v] = true;
                var affectedInfoParentShift = this._findAffectedSet(shiftList, {}, noUpSet, toObjectWithTrue(shiftList), toObjectWithTrue(childInfo.orderedChildren),
                                                                    misalignment, xcoord, true, false, 7, 3);

                var shiftList = childInfo.orderedChildren;
                var forbiddenList = [v, childhub];
                var affectedInfoChildShift = this._findAffectedSet(shiftList, {}, toObjectWithTrue(childInfo.orderedChildren), {}, toObjectWithTrue(forbiddenList),
                                                                   -misalignment, xcoord, true, false, 7, 3);

                var parentShiftAcceptable = this._isShiftSizeAcceptable( affectedInfoParentShift, false, 7, 3);
                var childShiftAcceptable  = this._isShiftSizeAcceptable( affectedInfoChildShift,  false, 7, 3);

                if (parentShiftAcceptable || childShiftAcceptable) {

                    improved = true;  

                    if ( parentShiftAcceptable &&
                         (!childShiftAcceptable || this._isShiftBetter(affectedInfoParentShift, affectedInfoChildShift)) ) {
                        var nodes = affectedInfoParentShift.nodes;
                        for (var i = 0; i < nodes.length; i++)
                            xcoord.xcoord[nodes[i]] += misalignment;
                    } else {
                        var nodes = affectedInfoChildShift.nodes;
                        for (var i = 0; i < nodes.length; i++)
                            xcoord.xcoord[nodes[i]] -= misalignment;
                    }

                    continue;
                }

                if (misalignment < 0) {
                    var leftShiftingNode = (this.DG.order.vOrder[leftParent] == this.DG.order.vOrder[v] - 1) ? leftParent : v;
                    var smallShift = Math.max(-xcoord.getSlackOnTheLeft(leftShiftingNode), misalignment);
                    if (smallShift == 0 || smallShift == misalignment) continue;
                } else {
                    var rightShiftingNode = (this.DG.order.vOrder[rightParent] == this.DG.order.vOrder[v] + 1) ? rightParent : v;
                    var smallShift = Math.min(xcoord.getSlackOnTheLeft(rightShiftingNode), misalignment);
                    if (smallShift == 0 || smallShift == misalignment) continue;
                }

                var shiftList = [v, childhub];
                if (this.DG.order.vOrder[leftParent]  == this.DG.order.vOrder[v] - 1 && !this.DG.GG.isVirtual(leftParent))
                    shiftList.unshift(leftParent);
                if (this.DG.order.vOrder[rightParent] == this.DG.order.vOrder[v] + 1 && !this.DG.GG.isVirtual(rightParent))
                    shiftList.push(rightParent);
                var noUpSet = {};
                noUpSet[v] = true;
                var affectedInfoParentShift = this._findAffectedSet(shiftList, {}, noUpSet, toObjectWithTrue(shiftList), toObjectWithTrue(childInfo.orderedChildren),
                                                                    smallShift, xcoord, true, false, 3, 2);

                if (this._isShiftSizeAcceptable( affectedInfoParentShift, false, 3, 2)) {
                    var nodes = affectedInfoParentShift.nodes;
                    for (var i = 0; i < nodes.length; i++)
                        xcoord.xcoord[nodes[i]] += smallShift;

                    continue;
                }
                //----------------------------------------------------------------
            }
        }

        this._compactGraph(xcoord);

        var iter = 0;
        var improved = true;
        while (improved && iter < 20) {
            improved = false;
            iter++;
            for (var k = 0; k < orderedRelationships.length; k++) {
                var v = orderedRelationships[k];

                var parents        = this.DG.GG.getInEdges(v);
                var orderedParents = this.DG.order.sortByOrder(parents);

                if (Math.abs(this.DG.order.vOrder[parents[0]] - this.DG.order.vOrder[parents[1]]) != 2) continue;

                var leftParentRightSide = xcoord.getRightEdge(orderedParents[0]);
                var rightParentLeftSide = xcoord.getLeftEdge (orderedParents[1]);

                var relX = xcoord.xcoord[v];
                var midX = Math.floor((leftParentRightSide + rightParentLeftSide)/2);

                if (relX == midX) continue;

                var childhub  = this.DG.GG.getRelationshipChildhub(v);

                var shiftSize = (midX - relX);
                var shiftList = [v, childhub];
                var noUpSet = {};
                noUpSet[v] = true;
                var affectedInfo = this._findAffectedSet(shiftList, {}, noUpSet, {}, {}, shiftSize, xcoord, true, false, 5, 3, this.DG.ranks[v]);

                if (this._isShiftSizeAcceptable( affectedInfo, false, 5, 3) && affectedInfo.minAffectedRank > this.DG.ranks[v]) {
                    var nodes = affectedInfo.nodes;
                    for (var i = 0; i < nodes.length; i++)
                        xcoord.xcoord[nodes[i]] += shiftSize;
                    improved = true;
                }
            }
        }


        this.DG.positions = xcoord.xcoord;

        timer.printSinceLast("=== Improvement runtime: ");

        this.DG.vertLevel = this.DG.positionVertically();
        this.DG.rankY     = this.DG.computeRankY(ranksBefore, rankYBefore);

        timer.printSinceLast("=== Vertical spacing runtime: ");
    },

    _compactGraph: function( xcoord, maxComponentSize ) {

        if (!maxComponentSize) maxComponentSize = Infinity;


        var iter = 0;
        var improved = true;
        while (improved && iter < 20)
        {
            improved = false;
            iter++;

            for (var rank = 1; rank < this.DG.order.order.length; rank++) {
                for (var order = 0; order < this.DG.order.order[rank].length - 1; order++) {
                    var v = this.DG.order.order[rank][order];

                    if (this.DG.GG.isChildhub(v)) break; 

                    var slack = xcoord.getSlackOnTheRight(v);
                    if (slack == 0) continue;

                    var DG = this.DG;
                    var excludeEdgesSpanningOrder = function(from, to) {
                        if (DG.ranks[from] == rank && DG.ranks[to] == rank) {
                            var orderFrom = DG.order.vOrder[from];
                            var orderTo   = DG.order.vOrder[to];
                            if ((orderFrom <= order && orderTo   > order) ||
                                (orderTo   <= order && orderFrom > order) ) {
                                return false;
                            }
                        }
                        return true;
                    };

                    var rightNeighbour = this.DG.order.order[rank][order+1];
                    var stopSet = {};
                    stopSet[rightNeighbour] = true;
                    var component = this.DG.findConnectedComponent(v, excludeEdgesSpanningOrder, stopSet, maxComponentSize );
                    var leftSide  = true;

                    if (component.stopSetReached) continue; 

                    if (component.size > maxComponentSize) {
                        component = this.DG.findConnectedComponent(rightNeighbour, excludeEdgesSpanningOrder, {}, maxComponentSize );
                        if (component.size > maxComponentSize) continue; 
                        leftSide  = false;
                    }

                    slack = leftSide ? xcoord.findVertexSetSlacks(component.component).rightSlack 
                                     : -xcoord.findVertexSetSlacks(component.component).leftSlack;

                    if (slack == 0) continue;
                    console.log("Moving: " + stringifyObject(component.component) + " by " + slack);

                    improved = true;

                    for (var node in component.component) {
                        if (component.component.hasOwnProperty(node)) {
                            xcoord.xcoord[node] += slack;
                        }
                    }
                }
            }

            if (!isFinite(maxComponentSize)) {
                for (var rank = 1; rank < this.DG.order.order.length; rank++) {
                    for (var order = 0; order < this.DG.order.order[rank].length; order++) {
                        var v = this.DG.order.order[rank][order];
                        if (this.DG.GG.isPerson(v)) break;        
                        if (this.DG.GG.isRelationship(v)) break;  
                        if (!this.DG.GG.isChildhub(v)) continue;  

                        var childhubX = xcoord.xcoord[v];

                        var childInfo = this.analizeChildren(v);
                        var childPositionInfo = this._computeDesiredChildhubLocation( childInfo, xcoord );
                        if (childhubX >= childPositionInfo.leftX && childhubX <= childPositionInfo.rightX) continue;

                        var shiftChhub = (childhubX > childPositionInfo.maxPreferred) ?
                                         (childPositionInfo.maxPreferred - childhubX) :
                                         (childPositionInfo.minPreferred - childhubX);

                        var noChildEdges = function(from, to) {
                            if (from == v) return false;
                            return true;
                        };
                        var stopSet = toObjectWithTrue(this.DG.GG.getOutEdges(v));
                        var component = this.DG.findConnectedComponent(v, noChildEdges, stopSet, Infinity );
                        if (component.stopSetReached) continue; 

                        var slack = (shiftChhub > 0) ? Math.min(shiftChhub, xcoord.findVertexSetSlacks(component.component).rightSlack) // slack on the right side of component
                                                     : Math.max(shiftChhub, -xcoord.findVertexSetSlacks(component.component).leftSlack);
                        if (slack == 0) continue;
                        console.log("Moving chhub: " + stringifyObject(component.component) + " by " + slack);

                        improved = true;

                        for (var node in component.component) {
                            if (component.component.hasOwnProperty(node)) {
                                xcoord.xcoord[node] += slack;
                            }
                        }
                    }
                }
            }
        }
    },

    _findAffectedSet: function( v_list, dontmove_set, noUp_set, noDown_set, forbidden_set, shiftSize, xcoord, stopAtVirtual, minimizeMovement, stopAtPersons, stopAtRels, stopAtRank ) {

        var nodes = toObjectWithTrue(v_list);

        var initialNodes = toObjectWithTrue(v_list);

        if (minimizeMovement) {
            for (var i = 0; i < v_list.length; i++) {
                noUp_set  [v_list[i]] = true;
                noDown_set[v_list[i]] = true;
            }
            for (var node in dontmove_set) {
                if (dontmove_set.hasOwnProperty(node)) {
                    var rank  = this.DG.ranks[node];
                    var order = this.DG.order.vOrder[node];

                    var from  = (shiftSize > 0) ? 0     : order + 1;
                    var to    = (shiftSize > 0) ? order : this.DG.order.order[rank].length;

                    for (var i = from; i < to; i++) {
                        var u = this.DG.order.order[rank][i];
                        dontmove_set[u] = true;
                        noUp_set[u]     = true;
                        noDown_set[u]   = true;
                    }
                }
            }
        }

        var numPersons     = 0;  
        var numRels        = 0;
        var numVirtual     = 0;
        var minRank        = Infinity;
        var forbiddenMoved = false;

        var toMove = new Queue();
        toMove.setTo(v_list);

        while(toMove.size() > 0) {
            if (stopAtPersons && numPersons > stopAtPersons) break;  
            if (stopAtRels    && numRels    > stopAtRels)    break;

            var nextV = toMove.pop();

            if (forbidden_set && forbidden_set.hasOwnProperty(nextV)) {
                forbiddenMoved = true;
                break;
            }

            if ( shiftSize > 0 ) {
                var slack = xcoord.getSlackOnTheRight(nextV);
                if (slack < shiftSize) {
                    var rightNeighbour = this.DG.order.getRightNeighbour(nextV, this.DG.ranks[nextV]);
                    if (!nodes.hasOwnProperty(rightNeighbour)) {
                        nodes[rightNeighbour] = true;
                        toMove.push(rightNeighbour);
                    }
                }
            } else {
                var slack = xcoord.getSlackOnTheLeft(nextV);
                if (slack < -shiftSize) {
                    var leftNeighbour = this.DG.order.getLeftNeighbour(nextV, this.DG.ranks[nextV]);
                    if (!nodes.hasOwnProperty(leftNeighbour)) {
                        nodes[leftNeighbour] = true;
                        toMove.push(leftNeighbour);
                    }
                }
            }

            if (noUp_set.hasOwnProperty(nextV) && noDown_set.hasOwnProperty(nextV)) continue;

            if (this.DG.ranks[nextV] < minRank && !initialNodes.hasOwnProperty(nextV)) {
                minRank = this.DG.ranks[nextV];
                if (stopAtRank && minRank < stopAtRank) break;
            }

            if (this.DG.GG.isRelationship(nextV)) {
                if (!initialNodes.hasOwnProperty(nextV)) numRels++;

                var chhub = this.DG.GG.getOutEdges(nextV)[0];
                if (!nodes.hasOwnProperty(chhub)) {
                    nodes[chhub] = true;
                    toMove.push(chhub);
                }

                if (minimizeMovement || noUp_set.hasOwnProperty(nextV)) continue;

                var parents = this.DG.GG.getInEdges(nextV);
                for (var i = 0; i < parents.length; i++) {
                    if (!dontmove_set.hasOwnProperty(parents[i]) && !nodes.hasOwnProperty(parents[i])) {
                        if ( (this.DG.order.vOrder[parents[i]] == this.DG.order.vOrder[nextV] + 1 && shiftSize < 0) ||  // if shiftSize > 0 it will get pushed anyway
                             (this.DG.order.vOrder[parents[i]] == this.DG.order.vOrder[nextV] - 1 && shiftSize > 0)) {
                            nodes[parents[i]] = true;
                            toMove.push(parents[i]);
                        }
                    }
                }
            }
            else
            if (this.DG.GG.isChildhub(nextV)) {
                var rel = this.DG.GG.getInEdges(nextV)[0];
                if (!nodes.hasOwnProperty(rel)) {
                    nodes[rel] = true;
                    toMove.push(rel);
                }

                if (minimizeMovement || noDown_set.hasOwnProperty(nextV)) continue;

                var childInfo    = this.analizeChildren(nextV);
                var positionInfo = this._computeDesiredChildhubLocation( childInfo, xcoord, nodes, shiftSize );

                var childhubX        = xcoord.xcoord[nextV];
                var shiftedChildhubX = childhubX + shiftSize;
                if (shiftedChildhubX == positionInfo.minPreferredWithShift || shiftedChildhubX == positionInfo.maxPreferredWithShift) continue;

                if (childhubX < positionInfo.minPreferredWithShift && shiftSize > 0 && shiftedChildhubX < positionInfo.minPreferredWithShift) continue;
                if (childhubX > positionInfo.maxPreferredWithShift && shiftSize < 0 && shiftedChildhubX > positionInfo.maxPreferredWithShift) continue;

                var children = this.DG.GG.getOutEdges(nextV);
                for (var j = 0; j  < children.length; j++) {
                    if (!dontmove_set.hasOwnProperty(children[j]) && !nodes.hasOwnProperty(children[j])) {
                        nodes[children[j]] = true;
                        toMove.push(children[j]);
                    }
                }
            }
            else
            if (this.DG.GG.isPerson(nextV)) {
                if (!initialNodes.hasOwnProperty(nextV)) numPersons++;

                if (!noDown_set.hasOwnProperty(nextV)) {
                    var rels = this.DG.GG.getOutEdges(nextV);
                    for (var j = 0; j < rels.length; j++) {
                        if (!dontmove_set.hasOwnProperty(rels[j]) && !nodes.hasOwnProperty(rels[j])) {
                            if ( (this.DG.order.vOrder[rels[j]] == this.DG.order.vOrder[nextV] + 1 && shiftSize < 0) ||  // if shiftSize > 0 it will get pushed anyway
                                 (this.DG.order.vOrder[rels[j]] == this.DG.order.vOrder[nextV] - 1 && shiftSize > 0)) {

                                 if ((shiftSize > 0 && xcoord.getSlackOnTheLeft(nextV) == 0) ||
                                     (shiftSize < 0 && xcoord.getSlackOnTheRight(nextV) == 0)) {
                                    nodes[rels[j]] = true;
                                    toMove.push(rels[j]);
                                 }
                            }
                        }
                    }
                }

                var twins = this.DG.GG.getAllTwinsOf(nextV);
                if (twins.length > 1) {
                    for (var t = 0; t < twins.length; t++) {
                        var twin = twins[t];
                        if (dontmove_set.hasOwnProperty(twin) || nodes.hasOwnProperty(twin)) continue;
                        toMove.push(twin);
                    }
                }

                if (noUp_set.hasOwnProperty(nextV)) continue;

                var inEdges = this.DG.GG.getInEdges(nextV);
                if (inEdges.length > 0) {
                    var chhub = inEdges[0];

                    if (dontmove_set.hasOwnProperty(chhub) || nodes.hasOwnProperty(chhub)) continue;

                    var childInfo    = this.analizeChildren(chhub);
                    var positionInfo = this._computeDesiredChildhubLocation( childInfo, xcoord, nodes, shiftSize );
                    var childhubX    = xcoord.xcoord[chhub];
                    if (childhubX == positionInfo.minPreferredWithShift || childhubX == positionInfo.maxPreferredWithShift) continue;
                    if (childhubX < positionInfo.minPreferred && shiftSize < 0 && childhubX < positionInfo.minPreferredWithShift) continue;
                    if (childhubX > positionInfo.maxPreferred && shiftSize > 0 && childhubX > positionInfo.maxPreferredWithShift) continue;

                    nodes[chhub] = true;
                    toMove.push(chhub);
                }
            }
            else
            if (this.DG.GG.isVirtual(nextV)) {
                if (!initialNodes.hasOwnProperty(nextV)) numVirtual++;

                if (stopAtVirtual && numVirtual > 0) break;

                if (!noUp_set.hasOwnProperty(nextV)) {
                    var v1 = this.DG.GG.getInEdges(nextV)[0];
                    if (!this.DG.GG.isPerson(v1) && !nodes.hasOwnProperty(v1) && !dontmove_set.hasOwnProperty(v1)) {
                        nodes[v1] = true;
                        toMove.push(v1);
                    }
                }
                if (!noDown_set.hasOwnProperty(nextV)) {
                    var v2 = this.DG.GG.getOutEdges(nextV)[0];
                    if (!this.DG.GG.isRelationship(v2) && !nodes.hasOwnProperty(v2) && !dontmove_set.hasOwnProperty(v2)) {
                        nodes[v2] = true;
                        toMove.push(v2);
                    }
                }
            }
        }

        var affectedNodes = [];
        for (var node in nodes) {
            if (nodes.hasOwnProperty(node)) {
                affectedNodes.push(node);
            }
        }
        return { "nodes": affectedNodes, "numPersons": numPersons, "numRelationships": numRels, "numVirtual": numVirtual,
                 "minAffectedRank": minRank, "forbiddenMoved": forbiddenMoved };
    },

    _computeDesiredChildhubLocation: function( childInfo, xcoord, nodesThatShift, shiftSize )
    {
        var leftMost  = childInfo.leftMostChildId;
        var rightMost = childInfo.rightMostChildId;

        var leftX  = xcoord.xcoord[leftMost];
        var rightX = xcoord.xcoord[rightMost];
        var middle = (leftX + rightX)/2;
        var median = (childInfo.orderedChildren.length == 3) ? xcoord.xcoord[childInfo.orderedChildren[1]] : middle;
        var minIntervalX = Math.min(middle, median);
        var maxIntervalX = Math.max(middle, median);

        var result = {"leftX": leftX, "rightX": rightX, "middle": middle, "median": median,
                      "minPreferred": minIntervalX, "maxPreferred": maxIntervalX };

        if (nodesThatShift) {
            var leftXShifted  = leftX  + (nodesThatShift.hasOwnProperty(leftMost)  ? shiftSize : 0);
            var rightXShifted = rightX + (nodesThatShift.hasOwnProperty(rightMost) ? shiftSize : 0);
            var middleShifted = (leftXShifted + rightXShifted)/2;
            var medianShifted = (childInfo.orderedChildren.length == 3)
                                ? (xcoord.xcoord[childInfo.orderedChildren[1]] + (nodesThatShift.hasOwnProperty(childInfo.orderedChildren[1]) ? shiftSize : 0))
                                : middleShifted;
            var minIntervalXShifted = Math.min(middleShifted, medianShifted);
            var maxIntervalXShifted = Math.max(middleShifted, medianShifted);

            result["minPreferredWithShift"] = minIntervalXShifted;
            result["maxPreferredWithShift"] = maxIntervalXShifted;
        }

        return result;
    },

    //=============================================================
    optimizeLongEdgePlacement: function()
    {

        var xcoord = new XCoord(this.DG.positions, this.DG);

        var longEdges = this.DG.find_long_edges();
        this.DG.try_straighten_long_edges(longEdges, xcoord);   

        var stillNotStraight = this.straighten_long_edges(longEdges, xcoord);  

        this.DG.try_straighten_long_edges(stillNotStraight, xcoord);

        this.DG.positions = xcoord.xcoord;
    },

    straighten_long_edges: function( longEdges, xcoord )
    {
        var stillNotStraight = [];

        for (var e = 0; e < longEdges.length; e++) {
            var chain = longEdges[e];
            do {
                var improved = false;
                var headCenter = xcoord.xcoord[chain[0]];
                for (var i = 1; i < chain.length; i++) {
                    var nextV      = chain[i];
                    var nextCenter = xcoord.xcoord[nextV];
                    if (nextCenter != headCenter) {
                        var head = chain.slice(0, i);
                        var tail = chain.slice(i);

                        var shiftHeadSize = nextCenter - headCenter;
                        var dontmove      = toObjectWithTrue(tail);
                        var affectedInfoHeadShift = this._findAffectedSet(head, dontmove, {}, {}, {}, shiftHeadSize, xcoord, true, true, 5, 3);

                        var shiftTailSize = headCenter - nextCenter;
                        var dontmove      = toObjectWithTrue(head);
                        var affectedInfoTailShift = this._findAffectedSet(tail, dontmove, {}, {}, {}, shiftTailSize, xcoord, true, true, 5, 3);

                        if (!this._isShiftSizeAcceptable( affectedInfoHeadShift, false, 5, 3) &&
                            !this._isShiftSizeAcceptable( affectedInfoTailShift, false, 5, 3) ) {
                            stillNotStraight.push(chain);
                            break;  
                        }

                        improved = true;   

                        if ( this._isShiftBetter(affectedInfoTailShift, affectedInfoHeadShift) ) {
                            var nodes = affectedInfoTailShift.nodes;
                            for (var i = 0; i < nodes.length; i++)
                                xcoord.xcoord[nodes[i]] += shiftTailSize;
                        } else {
                            var nodes = affectedInfoHeadShift.nodes;
                            for (var i = 0; i < nodes.length; i++)
                                xcoord.xcoord[nodes[i]] += shiftHeadSize;
                        }
                        break;
                    }
                }
            } while(improved);
        }

        return stillNotStraight;
    },

    _isShiftSizeAcceptable: function( shiftInfo, allowShiftVirtual, maxPersonNodes, maxRelNodes )
    {
        if (shiftInfo.forbiddenMoved) return false;
        if (!allowShiftVirtual && shiftInfo.numVirtual > 0) return false;
        if (shiftInfo.numPersons > maxPersonNodes) return false;
        if (shiftInfo.numRelationships > maxRelNodes) return false;
        return true;
    },

    _isShiftBetter: function( shiftInfo1, shiftInfo2 )
    {
        if (shiftInfo2.numVirtual > shiftInfo1.numVirtual) return true;
        if (shiftInfo2.numVirtual < shiftInfo1.numVirtual) return false;

        if (shiftInfo2.numPersons > shiftInfo1.numPersons) return true;
        if (shiftInfo2.numPersons < shiftInfo1.numPersons) return false;

        if (shiftInfo2.numRelationships > shiftInfo1.numRelationships) return true;
        return false;
    },
    //=============================================================

    moveToCorrectPositionAndMoveOtherNodesAsNecessary: function ( newNodeId, nodeToKeepEdgeStraightTo )
    {

        console.log("========== PLACING " + newNodeId);

        var originalDisturbRank = this.DG.ranks[newNodeId];

        var xcoord = new XCoord(this.DG.positions, this.DG);


        var leftBoundary  = xcoord.getLeftMostNoDisturbPosition(newNodeId);
        var rightBoundary = xcoord.getRightMostNoDisturbPosition(newNodeId);

        var desiredPosition = this.DG.positions[nodeToKeepEdgeStraightTo];             

        if (nodeToKeepEdgeStraightTo != newNodeId) {
            if (this.DG.ranks[nodeToKeepEdgeStraightTo] == originalDisturbRank) {     
                if (this.DG.order.vOrder[newNodeId] > this.DG.order.vOrder[nodeToKeepEdgeStraightTo])
                    desiredPosition = xcoord.getRightEdge(nodeToKeepEdgeStraightTo) + xcoord.getSeparation(newNodeId, nodeToKeepEdgeStraightTo) + xcoord.halfWidth[newNodeId];
                else {
                    desiredPosition = xcoord.getLeftEdge(nodeToKeepEdgeStraightTo) - xcoord.getSeparation(newNodeId, nodeToKeepEdgeStraightTo) - xcoord.halfWidth[newNodeId];
                    if (desiredPosition > rightBoundary)
                        desiredPosition = rightBoundary;
                }
            }
            else if (this.DG.GG.isPerson(newNodeId) && desiredPosition > rightBoundary)
                desiredPosition = rightBoundary;
        }

        var insertPosition = ( desiredPosition < leftBoundary ) ? leftBoundary : desiredPosition;

        xcoord.xcoord[newNodeId] = insertPosition;

        var shiftAmount = 0;
        if (insertPosition > desiredPosition)
            shiftAmount = (insertPosition - desiredPosition);

        var disturbedNodes = new Queue();
        disturbedNodes.push([newNodeId, shiftAmount]);

        var iterOuter = 0;
        var iter      = 0;

        var doNotTouch = {};
        var ancestors  = this.DG.GG.getAllAncestors(newNodeId);
        for (var node in ancestors) {
            doNotTouch[node] = true;
            var rank  = this.DG.ranks[node];
            var order = this.DG.order.vOrder[node];
            for (var i = 0; i < order; i++) {
                var u = this.DG.order.order[rank][i];
                doNotTouch[u] = true;
            }
        }

        var totalMove = {};   

        while ( disturbedNodes.size() > 0 && iterOuter < 5 ) {
            iterOuter++;

            var childrenMoved = {};   

            var numNodes             = this.DG.ranks.length;
            var maxExpectedMovements = numNodes*5;

            while ( disturbedNodes.size() > 0 && iter < maxExpectedMovements) {
                iter++; 


                var next     = disturbedNodes.pop();
                var v        = next[0];
                shiftAmount  = next[1];


                var type   = this.DG.GG.type[v];
                var vrank  = this.DG.ranks[v];
                var vorder = this.DG.order.vOrder[v];

                var position    = xcoord.xcoord[v];
                var rightMostOK = xcoord.getRightMostNoDisturbPosition(v);

                if (position > rightMostOK) {
                    var rightDisturbed = this.DG.order.order[vrank][vorder+1];

                    var toMove = position - rightMostOK;

                    xcoord.xcoord[rightDisturbed] += toMove;
                    totalMove[rightDisturbed]      = totalMove.hasOwnProperty(rightDisturbed) ? totalMove[rightDisturbed] + toMove : toMove;
                    disturbedNodes.push([rightDisturbed, toMove]);
                }

                if (v == newNodeId && type != TYPE.VIRTUALEDGE) continue;


                var inEdges  = this.DG.GG.getInEdges(v);
                var outEdges = this.DG.GG.getOutEdges(v);

                var skipInEdges = false;
                if ((type == TYPE.PERSON || type == TYPE.VIRTUALEDGE) && v == newNodeId) {
                    skipInEdges = true;
                }
                if (type == TYPE.VIRTUALEDGE) {
                    var inEdgeV = inEdges[0];
                    if (this.DG.ranks[inEdgeV] == vrank)
                        skipInEdges = true;
                }
                if (type == TYPE.RELATIONSHIP) {
                    skipInEdges = true;
                    if (inEdges.length == 2) {
                        var parent0 = inEdges[0];
                        var parent1 = inEdges[1];
                        var order0  = this.DG.order.vOrder[parent0];
                        var order1  = this.DG.order.vOrder[parent1];
                        if (order0 == vorder-1 && this.DG.GG.getOutEdges(parent0).length == 1 &&
                            this.DG.GG.getInEdges(parent0).length == 0 &&
                            !doNotTouch.hasOwnProperty(parent0) ) {
                            if (!totalMove.hasOwnProperty(parent0) || totalMove[parent0] < totalMove[v]) {
                                xcoord.xcoord[parent0] += shiftAmount;  
                                totalMove[parent0]      = totalMove.hasOwnProperty(parent0) ? totalMove[parent0] + shiftAmount : shiftAmount;
                            }
                        }
                        else if (order1 == vorder-1 && this.DG.GG.getOutEdges(parent1).length == 1 &&
                                 this.DG.GG.getInEdges(parent1).length == 0 &&
                                 !doNotTouch.hasOwnProperty(parent1)) {
                            if (!totalMove.hasOwnProperty(parent1) || totalMove[parent1] < totalMove[v]) {
                                xcoord.xcoord[parent1] += shiftAmount;  
                                totalMove[parent1]      = totalMove.hasOwnProperty(parent1) ? totalMove[parent1] + shiftAmount : shiftAmount;
                            }
                        }
                    }
                }

                if (!skipInEdges) {
                    for (var i = 0; i < inEdges.length; i++) {
                        var u     = inEdges[i];
                        var typeU = this.DG.GG.type[u];

                        if (doNotTouch.hasOwnProperty(u)) continue;
                        if (totalMove.hasOwnProperty(u) && totalMove[u] >= totalMove[v]) continue;

                        if (type == TYPE.PERSON && typeU == TYPE.CHILDHUB) {
                            if (childrenMoved.hasOwnProperty(u)) {
                                childrenMoved[u]++;
                            }
                            else {
                                childrenMoved[u] = 1;
                            }

                            continue;
                        }

                        if (typeU == TYPE.VIRTUALEDGE && xcoord.xcoord[u] == xcoord.xcoord[v]) continue;

                        var shiftU = totalMove.hasOwnProperty(u) ? Math.min(shiftAmount, Math.max(totalMove[v] - totalMove[u], 0)) : shiftAmount;

                        xcoord.xcoord[u] += shiftU;
                        totalMove[u]      = totalMove.hasOwnProperty(u) ? totalMove[u] + shiftU : shiftU;
                        disturbedNodes.push([u, shiftU]);
                    }
                }

                if (type == TYPE.CHILDHUB) {
                    var rightMostChildPos = 0;
                    for (var i = 0; i < outEdges.length; i++) {
                        var u   = outEdges[i];
                        var pos = xcoord.xcoord[u];
                        if (pos > rightMostChildPos)
                            rightMostChildPos = pos;
                    }
                    if (rightMostChildPos >= xcoord.xcoord[v]) continue; 
                }

                for (var i = 0; i < outEdges.length; i++) {
                    var u = outEdges[i];

                    var shiftU = totalMove.hasOwnProperty(u) ? Math.min(shiftAmount, Math.max(totalMove[v] - totalMove[u], 0)) : shiftAmount;

                    if (doNotTouch.hasOwnProperty(u)) continue;
                    if (totalMove.hasOwnProperty(u) && totalMove[u] >= totalMove[v]) continue;

                    if ( this.DG.ranks[u] == vrank ) continue;   

                    if (type == TYPE.RELATIONSHIP || type == TYPE.VIRTUALEDGE) {
                        var diff = xcoord.xcoord[v] - xcoord.xcoord[u];
                        if (diff <= 0) continue;
                        if (diff < shiftU)
                            shiftU = diff;
                    }

                    xcoord.xcoord[u] += shiftU;
                    totalMove[u]      = totalMove.hasOwnProperty(u) ? totalMove[u] + shiftU : shiftU;
                    disturbedNodes.push([u, shiftU]);
                }
            }


            for (var chhub in childrenMoved) {
                if (childrenMoved.hasOwnProperty(chhub)) {
                    chhub = parseInt(chhub);
                    if (doNotTouch.hasOwnProperty(chhub)) continue;
                    var children = this.DG.GG.getOutEdges(chhub);
                    if (children.length > 0 && children.length == childrenMoved[chhub]) {
                        var minShift = Infinity;
                        for (var j = 0; j < children.length; j++) {
                            if (totalMove[children[j]] < minShift)
                                minShift = totalMove[children[j]];
                        }
                        if (totalMove.hasOwnProperty(chhub)) {
                            if (totalMove[chhub] > minShift) continue;
                            minShift -= totalMove[chhub];
                        }
                        xcoord.xcoord[chhub] += minShift;
                        totalMove[chhub]      = totalMove.hasOwnProperty(chhub) ? totalMove[chhub] + minShift : minShift;
                        disturbedNodes.push([chhub, minShift]);
                    }
                }
            }

        } 

        this.DG.positions = xcoord.xcoord;

        console.log("PLACED/MOVED: " + newNodeId + " @ position " + this.DG.positions[newNodeId]);
    }
};

